Dans cette thèse nous appliquons des techniques provenant du calcul formel et de la théorie des langages afin d'améliorer les opérations élémentaires dans certaines tours de corps finis. Nous appliquons notre construction au problème du calcul d'isogénies entre courbes elliptiques et obtenons une variante plus rapide (à la fois en théorie et en pratique) de l'algorithme de Couveignes. Le document est divisé en quatre parties. Dans la partie I nous faisons des rappels d'algèbre et de théorie de la complexité. La partie II traite du principe de transposition : nous généralisons des idées de Bostan, Schost et Lecerf et nous montrons qu'il est possible de transposer automatiquement des programmes sans pertes en complexité-temps et avec une petite perte en complexité-espace. La partie III combine les résultats sur le principe de transposition avec des techniques classiques en théorie de l'élimination ; nous appliquons ces idées pour obtenir des algorithmes asymptotiquement optimaux pour l'arithmétique des tours d'Artin-Schreier de corps finis. Nous décrivons aussi une implantation de ces algorithmes. Enfin, dans la partie IV nous utilisons les résultats précédents afin d'accélérer l'algorithme de Couveignes et de comparer le résultat avec les autres algorithmes pour le calcul d'isogénies qui font l'état de l'art. Nous présentons aussi une nouvelle généralisation de l'algorithme de Couveignes qui calcule des isogénies de degré inconnu.

Cette thèse traite de la synchronisation des systèmes dynamiques.La synchronisation est étudiée pour une configuration de type maître-esclave, c'est-à-dire pour des systèmes couplés de façon unidirectionnelle. Ce type de configuration s'avère d'un intérêt tout particulier car elle correspond à des architectures de communications chiffrées un-vers-un ou un-vers-plusieurs. Une attention spécifique est portée sur l'autosynchronisation, comportement qui caractérise la synchronisation par le simple couplage maître-esclave et donc en l'absence de tout contrôle extérieur. Elle joue un rôle majeur dans les communications impliquant des chiffreurs par flot autosynchronisants. L'étude de l'autosynchronisation dans le contexte cryptographique s'appuie sur la théorie du contrôle. Un lien original entre l'autosynchronisation et le principe de chiffrement/déchiffrement en cryptographie est mis en évidence. Il fait appel à la propriété de platitude des systèmes dynamiques, un concept emprunté à l'automatique. On montre que les systèmes dynamiques plats définissent complètement l'ensemble des systèmes autosynchronisants et permettent d'élargir les structures existantes des chiffreurs autosynchronisants. La platitude est tout d'abord étudiée pour deux types de systèmes non linéaires~: les systèmes linéaires commutés et à paramètres variants (LPV). La caractérisation des sorties plates s'appuie sur le concept de semigroupes nilpotents et un algorithme performant est proposé. Une approche constructive pour réaliser des structures maître-esclave autosynchronisantes est proposée sur la base de systèmes plats et les notions d'inversibilité à gauche et à droite empruntées à la théorie du contrôle. Par la suite, l'autosynchronisation est étudiée dans le contexte booléen, privilégié en cryptographie.Elle est caractérisée en premier lieu au travers la notion d'influence. Ensuite, différentes représentations matricielles associées aux fonctions booléennes sont proposées. Ces représentations s'avèrent particulièrement intéressantes pour l'analyse des propriétés liées à la sécurité. Un lien entre l'autosynchronisation et les structures propres des représentations matricielles est établi. Une approche orientée graphes est finalement élaborée pour la caractérisation. De nouvelles constructions de structures autosynchronisantes en sont déduites et des éléments de sécurité sont discutés. Enfin, une plateforme de test à base de FPGA qui a été réalisée est décrite / This thesis deals with the synchronization of dynamical systems. The synchronization considered is called master-slave, that is, the dynamical systems are connected in a unidirectional way. This configuration is of interest because it corresponds to an architecture encountered in secured communications of type one-to-one or one-to-many. A special attention is paid to self-synchronization. A behaviour that characterizes synchronization achieved with a simple master-slave coupling and so, without any external control. It is a central feature of self-synchronizing stream ciphers. The study of self-synchronization in the cryptographic context relies on control theory. An original connection between self-synchronization and encryption/decryption is provided. It is based on the flatness property of dynamical systems, a property borrowed from automatic control. It is shown that flat dynamical systems completly define the set of all self-synchronizing systems and thus, enlarge the existing structures of self-synchronizing stream ciphers. Flatness is first of all studied for the case of two nonlinear systems: switched linear systems and linear parameter-varying (LPV) systems. Flatness caracterization is based on the concept of nilpotent semigroups and an efficient algorithm is provided. A constructive approach for self-synchronizing master-slave structures is proposed. It relies on the construction of flat systems as well as on left and right invertibility also borrowed from control theory. Then, self-synchronization is studied in the Boolean context which is preferred in cryptography. Self-synchronization is caracterized through the notion of influence. Several matrix representations of Boolean functions are proposed. These representations are especially interesting for security analysis. A connection between self-synchronization and the eigenstructures of these matrices is established. Then, a graph oriented approach is provided. New self-synchronizing constructions are deduced and security elements are discussed. Eventually, the description of a realized FPGA based test plateform is provided

Les primitives de la cryptographie à clé publique reposent sur la difficulté supposée de résoudre certains problèmes mathématiques. Dans ce travail, on s'intéresse à la cryptanalyse du problème du logarithme discret dans les sous-groupes multiplicatifs des corps finis. Les algorithmes de calcul d'index, utilisés dans ce contexte, nécessitent de résoudre de grands systèmes linéaires creux définis sur des corps finis de grande caractéristique. Cette algèbre linéaire représente dans beaucoup de cas le goulot d'étranglement qui empêche de cibler des tailles de corps plus grandes. L'objectif de cette thèse est d'explorer les éléments qui permettent d'accélérer cette algèbre linéaire sur des architectures pensées pour le calcul parallèle. On est amené à exploiter le parallélisme qui intervient dans différents niveaux algorithmiques et arithmétiques et à adapter les algorithmes classiques aux caractéristiques des architectures utilisées et aux spécificités du problème. Dans la première partie du manuscrit, on présente un rappel sur le contexte du logarithme discret et des architectures logicielles et matérielles utilisées. La seconde partie du manuscrit est consacrée à l'accélération de l'algèbre linéaire. Ce travail a donné lieu à deux implémentations de résolution de systèmes linéaires basées sur l'algorithme de Wiedemann par blocs : une implémentation adaptée à un cluster de GPU NVIDIA et une implémentation adaptée à un cluster de CPU multi-cœurs. Ces implémentations ont contribué à la réalisation de records de calcul de logarithme discret dans les corps binaires GF(2^{619}) et GF(2^{809} et dans le corps premier GF(p_{180}) / The security of public-key cryptographic primitives relies on the computational difficulty of solving some mathematical problems. In this work, we are interested in the cryptanalysis of the discrete logarithm problem over the multiplicative subgroups of finite fields. The index calculus algorithms, which are used in this context, require solving large sparse systems of linear equations over finite fields. This linear algebra represents a serious limiting factor when targeting larger fields. The object of this thesis is to explore all the elements that accelerate this linear algebra over parallel architectures. We need to exploit the different levels of parallelism provided by these computations and to adapt the state-of-the-art algorithms to the characteristics of the considered architectures and to the specificities of the problem. In the first part of the manuscript, we present an overview of the discrete logarithm context and an overview of the considered software and hardware architectures. The second part deals with accelerating the linear algebra. We developed two implementations of linear system solvers based on the block Wiedemann algorithm: an NVIDIA-GPU-based implementation and an implementation adapted to a cluster of multi-core CPU. These implementations contributed to solving the discrete logarithm problem in binary fields GF(2^{619}) et GF(2^{809}) and in the prime field GF(p_{180})

La sécurité des systèmes cryptographiques à clef publique repose sur la difficulté de résoudre certains problèmes mathématiques, parmi lesquels se trouve le problème du logarithme discret sur les corps finis GF(p^n). Dans cette thèse, nous étudions les variantes de l’algorithme de crible algébrique, number field sieve (NFS) en anglais, qui résolvent le plus rapidement ce problème, dans le cas où la caractéristique du corps est dite moyenne. NFS peut être divisé en quatre étapes principales : la sélection polynomiale, la recherche de relations, l’algèbre linéaire et le calcul d’un logarithme individuel. Nous décrivons ces étapes, en insistant sur la recherche de relations, une des étapes les plus coûteuses. Une des manières efficaces de réaliser cette étape est d’utiliser des algorithmes de crible. Contrairement au cas classique où la recherche de relations est réalisée dans un espace à deux dimensions, les corps finis que nous ciblons requièrent une énumération d’éléments dans un espace de plus grande dimension pour atteindre la meilleure complexité théorique. Il existe des algorithmes de crible efficaces en deux dimensions, mais peu pour de plus grandes dimensions. Nous proposons et analysons deux nouveaux algorithmes de crible permettant de traiter n’importe quelle dimension, en insistant particulièrement sur la dimension trois. Nous avons réalisé une implémentation complète de la recherche de relations pour plusieurs variantes de NFS en dimensions trois. Cette implémentation, qui s'appuie sur nos nouveaux algorithmes de crible, est diffusée au sein du logiciel CADO-NFS. Nous avons pu valider ses performances en nous comparant à des exemples de la littérature. Nous avons également été en mesure d’établir deux nouveaux records de calcul de logarithmes discrets, l'un dans un corps GF(p^5) de taille 324 bits et l'autre dans un corps GF(p^6) de taille 422 bits / The security of public-key cryptography relies mainly on the difficulty to solve some mathematical problems, among which the discrete logarithm problem on finite fields GF(p^n). In this thesis, we study the variants of the number field sieve (NFS) algorithm, which solve the most efficiently this problem, in the case where the characteristic of the field is medium. The NFS algorithm can be divided into four main steps: the polynomial selection, the relation collection, the linear algebra and the computation of an individual logarithm. We describe these steps and focus on the relation collection, one of the most costly steps. A way to perform it efficiently is to make use of sieve algorithms. Contrary to the classical case for which the relation collection takes place in a two-dimensional space, the finite fields we target require the enumeration of elements in a higher-dimensional space to reach the best theoretical complexity. There exist efficient sieve algorithms in two dimensions, but only a few in higher dimensions. We propose and study two new sieve algorithms allowing us to treat any dimensions, with an emphasis on the three-dimensional case. We have provided a complete implementation of the relation collection for some variants of the NFS in three dimensions. This implementation relies on our new sieve algorithms and is distributed in the CADO-NFS software. We validated its performances by comparing with examples from the literature. We also establish two new discrete logarithm record computations, one in a 324-bit GF(p^5) and one in a 422-bit GF(p^6)

Cette thèse se situe à l'interface de trois grands domaines : la combinatoire des mots, la théorie des automates et la théorie des nombres. Plus précisément, nous montrons comment des outils provenant de la combinatoire des mots et de la théorie des automates interviennent dans l'étude de problèmes arithmétiques concernant les séries formelles à coefficients dans un corps fini.Le point de départ de cette thèse est un célèbre théorème de Christol qui caractérise les séries de Laurent algébriques sur le corps F_q(T), l'entier q désignant une puissance d'un nombre premier p, en termes d'automates finis et dont l'énoncé est : « Une série de Laurent à coefficients dans le corps fini F_q est algébrique si et seulement si la suite de ses coefficients est engendrée par un p-automate fini ». Ce résultat, qui révèle dans un certain sens la simplicité de ces séries de Laurent, a donné naissance à des travaux importants parmi lesquels de nombreuses applications et généralisations.L'objet principal de cette thèse est, dans un premier temps, d'exploiter la simplicité de séries de Laurent algébriques à coefficients dans un corps fini afin d'obtenir des résultats diophantiens, puis d'essayer d'étendre cette étude à des fonctions transcendantes arithmétiquement intéressantes. Nous nous concentrons tout d'abord sur une classe de séries de Laurent algébriques particulières qui généralisent la fameuse cubique de Baum et Sweet. Le résultat principal obtenu pour ces dernières est une description explicite de leur développement en fraction continue, généralisant ainsi certains travaux de Mills et Robbins. Rappelons que le développement en fraction continue permet généralement d'obtenir des informations très précises sur l'approximation rationnelle ; les meilleures approximations étant obtenues directement à partir de la suite des quotients partiels. Malheureusement, il est souvent très difficile d'obtenir le développement en fraction continue d'une série de Laurent algébrique, que celle-ci soit donné par une équation algébrique ou par son développement en série de Laurent. La deuxième étude que nous présentons dans cette thèse fournit une information diophantienne à priori moins précise que la description du développement en fraction continue, mais qui a le mérite de concerner toutes les séries de Laurent algébriques (à coefficients dans un corps fini). L'idée principale est d'utiliser l'automaticité de la suite des coefficients de ces séries de Laurent afin d'obtenir une borne générale pour leur exposant d'irrationalité. Malgré la généralité de ce résultat, la borne obtenue n'est pas toujours satisfaisante. Dans certains cas, elle peut s'avérer plus mauvaise que celle provenant de l'inégalité de Mahler. Cependant, dans de nombreuses situations, il est possible d'utiliser notre approche pour fournir, au mieux, la valeur exacte de l'exposant d'irrationalité, sinon des encadrements très précis de ce dernier.Dans un dernier travail nous nous plaçons dans un cadre plus général que celui des séries de Laurent algébriques, à savoir celui des séries de Laurent dont la suite des coefficients a une « basse complexité ». Nous montrons que cet ensemble englobe quelques fonctions remarquables, comme les séries algébriques et l'inverse de l'analogue du nombre \pi dans le module de Carlitz. Il possède, par ailleurs, des propriétés de stabilité intéressantes : entre autres, il s'agit d'un espace vectoriel sur le corps des fractions rationnelles à coefficients dans un corps fini (ce qui, d'un point de vue arithmétique, fournit un critère d'indépendance linéaire), il est de plus laissé invariant par diverses opérations classiques comme le produit de Hadamard / This thesis looks at the interplay of three important domains: combinatorics on words, theory of finite-state automata and number theory. More precisely, we show how tools coming from combinatorics on words and theory of finite-state automata intervene in the study of arithmetical problems concerning the Laurent series with coefficients in a finite field.The starting point of this thesis is a famous theorem of Christol which characterizes algebraic Laurent series over the field F_q(T), q being a power of the prime number p, in terms of finite-state automata and whose statement is the following : “A Laurent series with coefficients in a finite field F_q is algebraic over F_q(T) if and only if the sequence of its coefficients is p-automatic”.This result, which reveals, somehow, the simplicity of these Laurent series, has given rise to important works including numerous applications and generalizations. The theory of finite-state automata and the combinatorics on words naturally occur in number theory and, sometimes, prove themselves to be indispensable in establishing certain important results in this domain.The main purpose of this thesis is, foremost, to exploit the simplicity of the algebraic Laurent series with coefficients in a finite field in order to obtain some Diophantine results, then to try to extend this study to some interesting transcendental functions. First, we focus on a particular set of algebraic Laurent series that generalize the famous cubic introduced by Baum and Sweet. The main result we obtain concerning these Laurent series gives the explicit description of its continued fraction expansion, generalizing therefore some articles of Mills and Robbins.Unfortunately, it is often very difficult to find the continued fraction representation of a Laurent series, whether it is given by an algebraic equation or by its Laurent series expansion. The second study that we present in this thesis provides a Diophantine information which, although a priori less complete than the continued fraction expansion, has the advantage to characterize any algebraic Laurent series. The main idea is to use some the automaticity of the sequence of coefficients of these Laurent series in order to obtain a general bound for their irrationality exponent. In the last part of this thesis we focus on a more general class of Laurent series, namely the one of Laurent series of “low” complexity. We prove that this set includes some interesting functions, as for example the algebraic series or the inverse of the analogue of the real number \pi. We also show that this set satisfy some nice closure properties : in particular, it is a vector space over the field over F_q(T).

Une variété algébrique est dite unirationnelle si elle est dominée par un espace projectif ; elle est dite séparablement unirationnelle si on peut prendre le morphisme précédent séparable. Cette dernière propriété n'a d'intérêt qu'en caractéristique positive. En reprenant la démonstration de Paranjape et Srinivas de l'unirationalité des hypersurfaces de degré très petit devant la dimension, nous remarquons qu'elle montre en fait l'unirationalité séparable. Nous nous intéressons aussi à la séparabilité des morphismes fournis par différentes constructions classiques de l'unirationalité des hypersurfaces cubiques.<br /><br />Dans la troisième partie, nous étudions la connexité rationnelle séparable : une variété projective lisse X sur un corps algébriquement clos est dite séparablement rationnellement connexe s'il existe une courbe rationnelle très libre (c'est-à-dire à fibré normal ample) sur X. Nous testons sur les hypersurfaces de Fermat de dimension N-1 et de degré q+1, où q est une puissance de la caractéristique du corps de base, la conjecture que toutes les hypersurfaces lisses de dimension N-1 et de degré plus petit que N sont séparablement rationnellement connexes. Nous montrons que pour N plus grand que 2q-1, l'hypersurface de Fermat de degré q+1 contient une courbe rationnelle très libre définie sur le sous-corps premier ; elle est donc séparablement rationnellement connexe.

L'algèbre linéaire numérique a connu depuis quelques décennies des développements intensifs <br />autant au niveau mathématique qu'informatique qui ont permis d'aboutir à de véritable standard <br />logiciel comme BLAS ou LAPACK.<br />Dans le cadre du calcul exact ou formel, la situation n'est pas aussi avancée, en particulier<br />à cause de la diversité des problématiques et de la jeunesse des progrès théoriques.<br />Cette thèse s'inscrit dans une tendance récente qui vise à fédérer des codes performants<br />provenant de bibliothèques spécialisées au sein d'une unique plateforme de calcul.<br />En particulier, l'émergence de bibliothèques robustes et portables comme GMP ou NTL pour le calcul exact <br />s'avére être un réel atout pour le développement d'applications en algèbre linéaire exacte.<br />Dans cette thèse, nous étudions la faisabilité et la pertinence de la réutilisation de codes spécialisés pour <br />développer une bibliothèque d'algèbre linéaire exacte performante, à savoir la bibliothèque LinBox.<br />Nous nous appuyons sur les mécanismes C++ de programmation générique (classes abtraites, classes templates)<br /> pour fournir une abstraction des composantes mathématiques et ainsi permettre le plugin de composants externes.<br />Notre objectif est alors de concevoir et de valider des boîtes à outils génériques haut niveau dans LinBox pour <br />l'implantation d'algorithmes en algèbre linéaire exacte. <br />En particulier, nous proposons des routines de calcul hybride "exact/numérique" pour des matrices denses sur un corps finis permettant d'approcher les performances obtenues par des bibliothèques numériques comme LAPACK.<br />À un plus haut niveau, ces routines nous permettent de valider la réutilisation de codes spécifiques sur un problème <br />classique du calcul formel: la résolution de systèmes linéaires diophantiens.<br />La bibliothèque LinBox est disponible à www.linalg.org.

Nous nous intéressons au nombre de points rationnels des variétés algébriques projectives sur un corps fini. Nous déterminons notamment la fonction zêta (et plus précisément les polynômes caractéristiques de l'endomorphisme de Frobenius sur les espaces de cohomologie étale l-adique) des courbes algébriques projectives sans autre hypothèse de lissité ou d'irréductibilité. Nous montrons la divisibilité de ces polynômes dans un revêtement plat de courbes connexes, que l'on peut interpréter comme un analogue de la conjecture d'holomorphie d'Artin sur les fonctions zêta de Dedekind des corps de nombres. Nous obtenons des bornes sur le nombre de points rationnels sur un corps fini dans un revêtement plat entre courbes algébriques projectives connexes, généralisant les bornes connues et notamment celle de Weil. Nous nous sommes également intéressé au problème du nombre de classes dans les corps de fonctions à une variable sur un corps fini. Nous avons établi un théorème de finitude en ce qui concerne les extensions totalement imaginaires d'extensions totalement réelles dont le nombre de classes d'idéaux du corps imaginaire est fixé . Dans le cas où ces extensions sont quadratiques, nous donnons une formule du nombre de classes relatif en terme de fonction L, ainsi qu'une formule liant cette fonction L à une somme de caractères de type Legendre dans le cas du nombre de classe 1. Si l'on suppose de plus que le groupe de Galois d'une telle extension est isomorphe au groupe de Klein, via la théorie du corps de classes ainsi que des factorisations de fonctions zêta et des estimations de régulateurs, nous déterminons ces corps via les extensions d'Artin-Schreier et les jacobiennes.

La complexité algorithmique est l'étude des ressources nécessaires -- le temps, la mémoire, ... -- pour résoudre un problème de manière algorithmique. Dans ce cadre, la théorie de la complexité algébrique est l'étude de la complexité algorithmique de problèmes de nature algébrique, concernant des polynômes.Dans cette thèse, nous étudions différents aspects de la complexité algébrique. D'une part, nous nous intéressons à l'expressivité des déterminants de matrices comme représentations des polynômes dans le modèle de complexité de Valiant. Nous montrons que les matrices symétriques ont la même expressivité que les matrices quelconques dès que la caractéristique du corps est différente de deux, mais que ce n'est plus le cas en caractéristique deux. Nous construisons également la représentation la plus compacte connue du permanent par un déterminant. D'autre part, nous étudions la complexité algorithmique de problèmes algébriques. Nous montrons que la détection de racines dans un système de n polynômes homogènes à n variables est NP-difficile. En lien avec la question " VP = VNP ? ", version algébrique de " P = NP ? ", nous obtenons une borne inférieure pour le calcul du permanent d'une matrice par un circuit arithmétique, et nous exhibons des liens unissant ce problème et celui du test d'identité polynomiale. Enfin nous fournissons des algorithmes efficaces pour la factorisation des polynômes lacunaires à deux variables.

La cryptologie consiste en l’étude des techniques utilisées par deux entités pour communiquer en secret en présence d’une troisième. Les propriétés mathématiques qui sous-tendent ces techniques garantissent que leur attaque reste infaisable en pratique par un adversaire malveillant. Ainsi, les protocoles s’appuient sur diverses hypothèses, comme la di fficulté présumée de factoriser des entiers ou de calculer le logarithme discret d’un élément arbitraire dans certains groupes. Cette thèse qui porte sur le problème du logarithme discret dans les corps finis s’articule autour de trois volets.Nous exposons les résultats théoriques associés au problème sans considération du groupe cible, détaillant ainsi les classes de complexité auxquelles il appartient ainsi que di fférentes approches pour tenter de le résoudre.L’étude du problème dans les corps finis commence en tant que telle par les corps présentant une caractéristique de petite taille relativement à l’ordre total du corps en question. Cette seconde partie résulte sur l’exposition d’un algorithme par représentation de Frobenius dont une application a aboutit au record actuel de calcul de logarithme discret en caractéristique 3.Pour les corps de moyenne ou grande caractéristiques, une autre méthode est requise. Le crible par corps de nombres (NFS) multiples obtient les complexités asymptotiques les plus basses pour un corps arbitraire. Un dernier chapitre introduit la notion de matrice presque creuse. L’élaboration d’un nouvel algorithme spécifique qui explicite le noyau d’une telle matrice facilite en pratique l’étape d’algèbre sous-jacente à toute variante de NFS. / Cryptography is the study of techniques for secure communication in the presence of third parties, also called adversaries. Such techniques are detailed in cryptosystems, explaining how to securely encode and decode messages. They are designed around computational hardness assumptions related to mathematical properties, making such algorithms hard to break in practice by any adversary. These protocols are based on the computational difficulty of various problems which often come from number theory, such as integer factorization or discrete logarithms computations. This manuscript focuses on the discrete logarithm problem in finite fields and revolves around three axes.First we detail classical results about the problem without any consideration to the target group. We deal with complexity classes and some general methods that do not need any information on the group.The study of the discrete logarithm problem in finite fields starts with small characteristic ones. The aim is to present a Frobenius representation algorithm that leads to the current discrete logarithm record in characteristic 3.For medium or large characteristics finite fields, another approach is required. The multiple number field sieve reaches the best asymptotic heuristic complexities for this double range of characteristics. We also introduce the notion of nearly sparse matrices. Designing a new algorithm dedicated to explicitly give the kernel of such a matrix eases in practice the linear algebra step of any variant of the number field sieve.