La cryptographie basée sur le logarithme discret a connu de nombreuses avancées dans les dix dernières années, notamment avec l'utilisation de tores algébriques introduite par Lenstra et Verheul. Ici on axe notre travail sur la facette constructive de ces idées et se penche sur le paramétrage de ces structures. Van Dijk et Woodruff ont récemment proposé une solution pour représenter de manière compacte une famille de points d'un tore algébrique. Afin d'améliorer la complexité asymptotique de cet algorithme, on a recours à plusieurs outils. D'une part on utilise un nouveau type de bases pour les extensions de corps finis, les bases normales elliptiques dues à Couveignes et Lercier. Par ailleurs, les tailles des objets manipulés font intervenir des polynômes cyclotomiques et leurs inverses modulaires. L'amplitude de leurs coefficients intervient directement dans l'étude de complexité. Dans le cas où leurs indices sont des diviseurs d'un produit de deux nombres premiers, on parvient à des bornes voire des expressions explicites pour ces coefficients, qui permettent de conclure quant à l'amélioration du coût de communication dans des protocoles cryptographiques comme une négociation de clefs multiples de Diffie-Hellman.

Ce mémoire est composé de deux grandes parties. Dans la première, nous simulons le fonctionnement d'automates cellulaires par différents modèles de calcul parallèle comme les PRAM, les XPRAM et les machines spatiales. Nous obtenons ainsi différentes preuves de l'universalité de ces modèles. Nous tirons quelques conséquences de ces résultats du point de vue de la calculabilité et de la complexité. Dans la seconde partie, nous considérons les automates cellulaires définis sur des graphes de Cayley finis. Nous rappelons la simulation de Róka qui permet de mimer le fonctionnement d'un tore hexagonal d'automates par un tore d'automates de dimension deux. Nous décrivons ensuite différentes manières de plonger un tore d'automates de dimension deux dans un anneau d'automates. Nous déduisons de ces résultats la simulation de tores de dimension finie par un anneau d'automates et celle d'un tore hexagonal d'automates par un anneau d'automates.

Dans cette thèse, nous résolvons la conjecture de Fuglede sur le corps des nombres p-adiques, et étudions certaines propriétés aléatoires des suites liées à la conjecture de Sarnak, ainsi que leur propriétés oscillantes. Dans la première partie, nous prouvons d'abord la conjecture de Fuglede pour des ensembles ouverts compacts dans Q_p. Celle-ci indique qu'un ensemble ouvert compact dans Q_p est un ensemble spectral si et seulement s'il pave Q_p par translation. Il est également prouvé qu'un ensemble ouvert compact est un ensemble spectral (ou une tuile) si et seulement s'il est p-homogène. Nous caractérisons les ensembles spectraux dans Z / p^n Z ( p>1 premier, n>0 entier) par la propriété de pavage et aussi par leur homogénéité. Finalement, nous montrons la conjecture de Fuglede dans Q_p sans la restriction d'être ouvert compact en montrant que tout ensemble spectral ou toute tuile doivent être ouvert et compact à un ensemble de mesure nulle près. Dans la seconde partie, nous donnons d'abord plusieurs définitions équivalentes d'une suite oscillante en termes de disjonction de différents systèmes dynamiques sur des tores. Ensuite, nous définissons la propriété de Chowla et la propriété de Sarnak pour des suites numériques prenant des valeurs 0 ou des nombres complexes de module 1. Nous prouvons que la propriété de Chowla implique la propriété de Sarnak. Il est également prouvé que pour Lebesgue presque tout b> 1, la suite (e^{2 pi b^n})_{n in N} partage la propriété de Chowla et est par conséquent orthogonale à tout système dynamique topologique d'entropie nulle. Nous discutons également si les échantillons d'une suite aléatoire donnée ont presque sûrement la propriété de Chowla. Nous construisons certaines suites aléatoires dépendantes ayant presque sûrement la propriété de Chowla / In this thesis, we solve Fuglede's conjecture on the field of p-adic numbers, and study some randomness and the oscillating properties of sequences related to Sarnak's conjecture. In the first part, we first prove Fuglede's conjecture for compact open sets in the field Q_p which states that a compact open set in Q_p is a spectral set if and only if it tiles Q_p by translation. It is also proved that a compact open set is a spectral set (or a tile) if and only if it is p-homogeneous. We characterize spectral sets in Z/p^n Z (p>1 prime, n>0 integer) by tiling property and also by homogeneity. Finally, we prove Fuglede's conjecture in Q_p without the assumption of compact open sets and also show that the spectral sets (or tiles) are the sets which differ by null sets from compact open sets. In the second part, we first give several equivalent definitions of oscillating sequences in terms of their disjointness from different dynamical systems on tori. Then we define Chowla property and Sarnak property for numerical sequences taking values 0 or complex numbers of modulus 1. We prove that Chowla property implies Sarnak property. It is also proved that for Lebesgue almost every b>1, the sequence (e^{2 pi b^n})_{n in N} shares Chowla property and consequently is orthogonal to all topological dynamical systems of zero entropy. We also discuss whether the samples of a given random sequence have almost surely Chowla property. Some dependent random sequences having almost surely Chowla property are constructed

Nous étudions le comportement analytique de la fonction zêta associée à une certaine hauteur anticanonique sur une variété torique projective et lisse, le corps de définition étant un corps global de caractéristique positive. Ce comportement est étroitement lié à l'évolution asymptotique du nombre de points de hauteur bornée sur la variété. Manin et ses collaborateurs ont proposé des formules conjecturales pour le nombre de points de hauteur bornée sur une variété de Fano ou presque de Fano. Dans le cas des variétés toriques définies sur un corps de nombres ces formules ont été démontrées par Batyrev et Tschinkel, puis redémontrées par Salberger sous des hypothèses plus restrictives mais par une méthode entièrement différente. Nous nous intéressons donc dans cette thèse à la version fonctionnelle de ces résultats. Nous commençons par traiter le cas d'une variété torique déployée, en nous inspirant de la méthode de Salberger, basée sur une paramétrisation des points rationnels donnée par les torseurs universels ainsi que sur une inversion de Möbius. Nous expliquons ensuite comment les techniques utilisées dans cette situation peuvent s'appliquer aussi à un contexte motivique, mais notre calcul repose en partie sur une hypothèse non demontrée. Enfin pour examiner le cas de la compactification d'un tore non déployé nous adaptons au cas fonctionnel l'approche de Batyrev et Tshinkel. Leur idée est d'utiliser la formule de Poisson pour obtenir une représentation intégrale de la fonction zêta des hauteurs, intégrale que l'on évalue à l'aide du théorème des résidus. Nous obtenons une formule conforme aux prédictions de Manin et al., modulo le calcul d'un invariant du tore, invariant spécifique à la caractéristique non nulle. Nous n'avons pu mener à bien le calcul de cet invariant que pour des familles particulières de tores algébriques, et dans ce cas la formule obtenue est celle attendue. La question de savoir si la situation est la même pour un tore algébrique quelconque reste ouverte.

Les systèmes intégrables toriques sont des systèmes intégrables dont toutes les composantes de l'application moment sont périodiques de même période. Il s'agit donc de variétés symplectiques munies d'actions Hamiltoniennes de tores. Au début des années 80, Atiyah-Guillemin-Sternberg ont démontré que l'image de l'application moment était un polytope convexe à face rationnelles. Peu de temps après, Delzant a démontré que dans le cas intégrable qui nous intéresse, ce polytope caractérisait entièrement le système : la variété symplectique comme l'action du tore. Le champs d'étude s'est ensuite élargi aux systèmes dits semi-toriques. Ce sont des systèmes intégrables dont toutes les composantes de l'application moment sauf une sont périodiques de même période. En outre, pour simplifier l'étude de ces systèmes, on demande que tous les points critiques du systèmes soient non-dégénérés, et sans composante hyperbolique pour la hessienne. En revanche les points critiques des systèmes semi-toriques peuvent comporter des composantes dites "foyer-foyer". Celles-ci ont une dynamique plus riche que les singularités elliptiques, mais conservent certaines propriétés qui rendent leur analyse plus aisée que les singularités hyperboliques. San Vu-Ngoc et Alvaro Pelayo ont réussi à étendre pour ces systèmes semi-toriques les résultats d'Atiyah-Guillemin-Sternberg et Delzant en dimension 2. L'objectif de cette thèse est de proposer une extension de ces résultats en dimension quelconque, à commencer par la dimension 3. Les techniques utilisées relèvent de l'analyse comme de la géométrie symplectique, ainsi que de la théorie de Morse dans des espaces différentiels stratifiés. / Semi-toric integrable systems are integrable systems whose every component of the moment map are periodic of the same period. They are symplectic manifolds endowed with a Hamiltonian torus actions. At the beginning of the 80's, Atiyah-Guillemin-Sternberg proved that the image of the moment map was a polytope with rational faces. A bit after that, Delzant showed that in the integrable case that matters to us, this polytope characterized entirely the system, that is, the symplectic manifold as well as the torus action. Next, field of study widened to semi-toric systems. They are integrable systems whose all components except one are periodic with the same period. Moreover, to simplify their study, we ask that these systems have only non-degenerate critical points without hyperbolic components. On the other hand, critical points of semi-toric systems can have so-called ''focus-focus'' components. They have a richer dynamic than elliptic singularities, but it retains some properties that makes them easier to study than hyperbolic singularities. San Vu-Ngoc and Alvaro Pelayo have managed to extend to these semi-toric systems the results of Atiyah-Guillemin-Sternberg and Delzant in dimension 2. The objective of this thesis is to propose an extension of these results to any dimension, starting with dimension 3. Techniques involved are analysis as well as symplectic geometry, and Morse theory in stratified differential spaces.

Nous mettons en évidence une condition géométrico-dynamique minimale créant de l'hyperbolicité au voisinage d'un tore homocline transverse partiellement hyperbolique dans un système Hamiltonien presque intégrable à trois degrés de liberté. On en déduit une généralisation du théorème de dynamique symbolique d'Easton. Nous donnons ensuite une estimation optimale du temps de diffusion d'Arnold le long d'une chaîne de transition dans les systèmes Hamiltoniens initialement hyperboliques à trois degrés de liberté en utilisant une chaîne d'orbites périodiques hyperboliques sous-jacente. <br />Nous décrivons ensuite géométriquement à partir d'un système Hamiltonien presque intégrable à trois degrés de liberté à deux paramètres dû à Chirikov, un mécanisme de diffusion mettant en jeu un réseau de plans résonnants parallèles et voisins et un plan résonnant transversal au réseau. Ainsi, nous montrons qu'en dessous d'un certain seuil atteint par le paramètre prépondérant, on peut construire une orbite de transition dérivant en action à travers ce réseau modulationnel. Un des scénarii envisagés, le mécanisme de diffusion modulationnelle, basé sur l'existence de connexions hétéroclines entre tores partiellement hyperboliques issus de deux plans résonnants distincts est valide lorsqu'une condition de chevauchement est vérifiée. <br />Nous étudions enfin le modèle bidimensionnel décrivant un écoulement laminaire avec convection mixte entre deux plaques planes puis dans un tube vertical. Avec des conditions aux bords réduites, nous montrons via le théorème de la variété centrale qu'il existe dans le premier cas une bifurcation de pitchfork pour une valeur critique du nombre de Rayleigh.

La dynamique des systèmes hyperboliques est considérée bien comprise du point de vue topologique aussi bien que du point de vue stochastique. S. Smale et R. Abraham ont donné un exemple montrant que, en général, les systèmes hyperboliques ne sont pas denses parmi tous les systèmes diffélrentiables. Dans les années 1970, M. Brin et Y. Pesin ont proposé une nouvelle notion: hyperbolicité partielle pour affaiblir la notion d’hyperbolicité. Un but de cette thèse est de comprendre la dynamique de certains systèmes partiellement hyperboliques du point de vue stochastique aussi bien que du point de vue topologique. Du point de vue stochastique, nous démontrons les résultats suivants: — Il existe un sous-ensemble U ouvert et dense de difféomorphismes non hyperboliques robustement transitifs loin de tangences homocliniques, tels que pour tout f ∈ U, il existe des mesures ergodiques non hyperboliques qui sont limite faible des mesures périodiques, avec un seul exposant de Lyapunov nul, et dont les supports sont la variété entière; — Il existe un sous-ensemble ouvert et dense de l’ensemble des difféomorphismes partiellement hyperboliques (mais non hyperboliques) de dimension centrale un dont les feuilletages forts sont robustement minimaux, de sorte que la fermeture de l’ensemble des mesures ergodiques est l’union de deux convexes qui sont la fermeture des ensembles de mesures ergodiques hyperboliques de deux s-indices différents respectivement; ces deux ensembles convexes se coupent le long de la fermeture de l’ensemble des mesures ergodiques non hyperboliques. Par conséquent, toute mesure ergodique non hyperbolique est approchée par des mesures périodiques. C’est le cas pour une perturbation robustement transitive du temps un d’un flot d’Anosov transitif, ou du produit fibré d’un difféomorphisme d’Anosov sur le tore par une rotation du cercle. Ces résultats sont basés sur des résultats locaux dont les démonstrations impliquent beaucoup de définitions techniques. Du point de vue topologique, pour tout flot d’Anosov non transitif sur des variétés de dimension 3 orientables, nous construisons de nouveaux difféomorphismes partiellement hyperboliques en composant le temps t des flots d’Anosov (pour t > 0 large) avec des twists de Dehn le long des tores transversaux. Ces nouveaux difféomorphismes partiellement hyperboliques sont robustement dynamiquement cohérents. Cela généralise dans un cas général le processus spécial dans [BPP] pour construire de nouveaux difféomorphismes partiellement hyperboliques. De plus, nous démontrons que pour les nouveaux difféomorphismes partiellement hyperboliques que nous avons construits, leurs feuilletages centraux sont topologiquement équivalentes aux flots d’Anosov utilisés pour les construire. En conséquence, la structure des feuilles centrales des nouveaux difféomorphismes partiellement hyperboliques est la même que la structure des orbites d’un flot d’Anosov. La présence de mesures ergodiques non hyperboliques montre la non hyperbolicité des systémes. Dans cette thése, nous cherchons également à comprendre: dans quelle mesure la présence de mesures ergodiques non hyperboliques peut-elle caractériser le degré de non-hyperbolicité des systèmes? Nous démontrons que, pour les difféomorphismes génériques, si une classe homoclinique contient des orbites périodiques d’indices différents et sans certaines dominations, il existe une mesure ergodique non hyperbolique avec plus d’un exposant de Lyapunov qui s’annule et dont le support est la classe homoclinique entière. Le nombre d’exposants de Lyapunov nuls montre combien d’hyperbolicité a été perdue dans un tel type de systèmes. / The dynamics of hyperbolic systems is considered well understood from topological point of view as well as from stochastic point of view. S. Smale and R. Abraham gave an example showing that, in general, the hyperbolic systems are not dense among all differentiable systems. In 1970s, M. Brin and Y. Pesin proposed a new notion: partial hyperbolicity to release the notion of hyperbolicity. One aim of this thesis is to understand the dynamics of certain partially hyperbolic systems from stochastic point of view as well as from topological point of view. From stochastic point of view, we prove the following results: — There exists an open and dense subset U of robustly transitive nonhyperbolic diffeomorphisms far from homoclinic tangency, such that forany f ∈ U, there exist non-hyperbolic ergodic measures as the weak*- limit of periodic measures, with only one vanishing Lyapunov exponent, and whose supports are the whole manifold; — There exists an open and dense subset of partially hyperbolic (but nonhyperbolic) diffeomorphisms with center dimension one whose strong foliations are robustly minimal, such that the closure of the set of ergodic measures is the union of two convex sets which are the closure of the sets of hyperbolic ergodic measures of two different s-indices respectively; these two convex sets intersect along the closure of the set of nonhyperbolic ergodic measures. As a consequence, every non-hyperbolic ergodic measure is approximated by periodic measures. That is the case for robustly transitive perturbation of the time one map of a transitive Anosov flow, or of the skew product of an Anosov torus diffeomorphism by a rotation of the circle. These results are based on some local results whose statements involve in lots of technical definitions. From topological point of view, for any non-transitive Anosov flow on orientable 3-manifolds, we build new partially hyperbolic diffeomorphisms by composing the time t-map of the Anosov flow (for t > 0 large) with Dehn twists along transverse tori. These new partially hyperbolic diffeomorphisms are robustly dynamically coherent. This generalizes the special process in [BPP] for constructing new partially hyperbolic diffeomorphisms to a general case. Furthermore, we prove that for the new partially hyperbolic diffeomorphisms we built, their center foliations are topologically equivalent to the Anosov flows used for building them. As a consequence, one has that the structure of the center leaves of the new partially hyperbolic diffeomorphisms is the same asthe structure of the orbits of an Anosov flow. The presence of non-hyperbolic ergodic measures shows the non-hyperbolicity of the systems. In this thesis, we also attempt to understand: to what extent, can the presence of non-hyperbolic ergodic measures character how far from hyperbolicity the systems are? We prove that, for generic diffeomorphisms, if a homoclinic class contains periodic orbits of different indices and without certain dominations, then there exists a non-hyperbolic ergodic measure with more than one vanishing Lyapunov exponents and whose support is the whole homoclinic class. The number of vanishing Lyapunov exponents shows how much hyperbolicity has been lost in such kind of systems.