Search

This thesis is devoted to the study of the lower existence bounds on the genus of hyperelliptic curves over a fixed finite field. More precisely, given an integer N, we ask: what is the minimum number G such that for any g bigger than G there is a genus g hyperelliptic curve having exactly N rational points?The first part of the manuscript deals with so called pointless curves, i.e. when N equals zero. Using some explicit constructions, for each characteristic we establish a new bound that depends linearly on the size of the ground finite field.In the second part one considers the general case. Here, when the characteristic is odd and N is strictly positive, a new quasilinear bound on the genera is obtained by means of implicit constructions.The third part completes the above theoretical results. We propose a new approach to the computer search of hyperelliptic curves over small finite fields of odd characteristic by exploiting the machinery of binary linear codes.This thesis was held under the direction of Professor Alexey Zykin at the University of French Polynesia (2015—2017)., Cette thèse est consacrée à l’étude des bornes inférieures sur le genre des courbes hyperelliptiques sur un corps fini. Plus précisément, étant donné un entier N, nous demandons : quel est le nombre minimum G tel que pour tout g plus grand que G il existe une courbe hyperelliptique de genre g ayantexactement N points rationnels ?La première partie du manuscrit traite des courbes sans points rationnels, c’est-à-dire lorsque N est égal à zéro. En utilisant certaines constructions explicites, nous établissons pour chaque caractéristique une nouvelle borne qui dépend linéairement de la taille du corps fini.Dans la deuxième partie, on considère le cas général. Ici, lorsque la caractéristique est impaire et que N est strictement positif, une nouvelle borne quasi-linéaire sur les genres est obtenue à l’aide de constructions implicites.La troisième partie complète les résultats théoriques ci-dessus. Nous proposons une nouvelle approche de la recherche informatique des courbes hyperelliptiques sur les petits corps finis de caractéristique impaire en exploitant la machinerie des codes linéaires binaires.Cette thèse a été réalisée sous la direction du Professeur Alexey Zykin à l’Université de Polynésie française (2015—2017).

Finite fields are ubiquitous in cryptography and coding theory, two fields that are of utmost importance in modern communications. For that reason, it is crucial to represent finite fields and compute in them in the most efficient way possible. In this thesis, we investigate the arithmetic of finite field extensions in two different and independent ways.In the first part, we study the arithmetic of one fixed finite field extension F_{p^k}. When estimating the complexity of an algorithm in a finite field extension, we often count the arithmetic operations that are needed in the base field F_p. In such a model, all operations have the same unit cost. This is known as the algebraic complexity model. Nevertheless, it is known that multiplications are more expensive, i.e. take more time, than additions. For that reason, alternative models were studied, such as the bilinear complexity model, in which the assumption is that additions have no cost, thus we only count the multiplications. To have an efficient multiplication algorithm in the extension F_{p^k}, research has been done to obtain formulas in which the number of multiplications in the base field F_p are minimized. The optimal number of such multiplication is, by definition, the bilinear complexity of the multiplication in F_{p^k}. Finding the exact value of the bilinear complexity of the multiplication in finite field extensions is hard, but there exist algorithms to find optimal formulas in small dimension. Asymptotically, there exist different algorithms that give formulas that are not necessarily optimal but still give a linear upper bound on the bilinear complexity in the degree of the extension. We generalize these results to a new kind of complexity, called the hypersymmetric complexity, that is linked with formulas possessing extra properties of symmetry. We provide an ad hoc algorithm finding hypersymmetric formulas in small dimension, as well as an implementation and experimental results. Generalizing the proofs of the literature, we also prove that the hypersymmetric complexity is still linear in the degree of the extension.In the second part, we work with multiple finite field extensions simultaneously. In most computer algebra systems, it is possible to deal with finite fields, but two arbitrary extensions are often seen as independent objects, and the links between them are not necessarily accessible to the user. Our goal in this part is to construct an efficient data structure to represent multiple extensions, and the embeddings between them. We also want the embeddings to be compatible, i.e. if we have three integers a, b, c such that a | b | c, we want the composition of the embeddings from F_{p^a} to F_{p^b} and F_{p^b} to F_{p^c} to be equal to the embedding from F_{p^a} to F_{p^c}. We call this data structure a lattice of compatibly embedded finite fields. We provide an implementation of the Bosma-Canon-Steel framework, a lattice of compatibly embedded finite fields that was only available in MAGMA, as well as experimental results. After this work, we also added the Bosma-Canon-Steel framework to the computer algebra system Nemo.Another popular method to obtain lattices of compatibly embedded finite fields is to use Conway polynomials. It is quite efficient but the extensions have to be defined using these precomputed special polynomials to obtain compatibility between embeddings. Inspired by both the Bosma-Canon-Steel framework and the Conway polynomials, we construct a new kind of lattice, that we call standard lattice of compatibly embedded finite fields. This construction allows us to use arbitrary finite field extensions, while being rather efficient. We provide a detailed complexity analysis of the algorithms involved in this construction, as well as experimental results to show that the construction is practical.; Les corps finis sont omniprésents en cryptographie et en théorie des codes, deux domaines de première importance dans les communications modernes. Ainsi, il est crucial de représenter les corps finis et d’y faire des calculs de la façon la plus efficace possible. Dans cette thèse, nous travaillons sur l’arithmétique des extensions de corps finis, de deux manières différentes et indépendantes.Dans la première partie, nous étudions l’arithmétique d’une unique extension de corps fini F_{p^k}. Lorsqu’on souhaite estimer la complexité d’un algorithme dans une extension, on compte souvent les opérations arithmétiques qui sont effectuées dans le corps de base F_p. Dans un tel modèle, toutes les opérations ont le même coût. Ce modèle est connu sous le nom de complexité algébrique. Néanmoins, on sait que la multiplication est une opération plus coûteuse que l’addition. Pour cette raison, des modèles alternatifs ont été étudiés, comme par exemple celui de la complexité bilinéaire, dans lequel on fait l’hypothèse que les additions n’ont aucun coût, et on compte donc uniquement les multiplications. Pour avoir une multiplication efficace dans l’extension F_{p^k}, des recherches ont été menées pour obtenir des formules dans lesquelles le nombre de multiplications dans le corps de base F_p est minimal. Le nombre optimal de multiplications nécessaires est, par définition, la complexité bilinéaire de la multiplication dans l’extension F_{p^k}. Trouver la valeur exacte de la complexité bilinéaire d’une extension est difficile, mais il existe des algorithmes pour chercher des formules optimales en petite dimension. Asymptotiquement, d’autres algorithmes trouvent des formules qui ne sont pas nécessairement optimales, mais qui donnent une borne supérieur linéaire en le degré de l’extension pour la complexité bilinéaire. Nous généralisons ces résultats à un nouveau type de complexité, qualifiée d’hypersymétrique, qui est liée à des formules possédant plus de symétries. Nous fournissons un algorithme pour trouver des formules hypersymmétrique, ainsi qu’une implémentation et son analyse. Nous prouvons également que la complexité hypersymmétrique est elle aussi linéaire. Dans la seconde partie, nous étudions plusieurs extensions simultanément. Dans la plupart des systèmes de calcul formel, il est possible de travailler avec des corps finis, mais deux extensions arbitraires sont souvent considérées comme des objets indépendants, et les liens entre ces extensions ne sont pas nécessairement accessibles à l’utilisateur ou l’utilisatrice. Notre but dans cette partie est de construire une structure de donnée efficace pour représenter plusieurs extensions, ainsi que les plongements entre elles. Nous voulons aussi que ces plongements soient compatibles, c’est-à-dire que si a, b, c sont trois (avec a | b | c), la composition entre les plongements de F_{p^a} vers F_{p^b} et F_{p^b} vers F_{p^c} doit être égale au plongement de F_{p^a} dans F_{p^c}. Nous appelons cette structure de donnée un réseau de corps finis compatiblement plongés. Nous donnons une implémentation de l’algorithme de Bosma-Canon-Steel, qui permet d’avoir un réseau compatible, et qui était uniquement disponible dans MAGMA. Après ce travail, nous avons ajouté cet algorithme au système de calcul formel Nemo. Une autre méthode populaire pour obtenir des réseaux compatibles vient des polynômes de Conway. C’est une manière efficace d’obtenir des plongements, mais les extensions doivent alors être définies en utilisant ces polynômes précalculés si l’on veut garantir la compatibilité. Inspiré par ces polynômes et l’algorithme de Bosma-Canon-Steel, nous proposons une nouvelle construction nommée réseau standard de corps finis compatiblement plongés. Cette dernière nous permet d’utiliser des corps finis arbitraires, tout en restant efficace. Nous analysons en détail la complexité de nos algorithmes, et donnons une implémentation montrant que notre construction peut être utilisée en pratique.

In the thesis two tasks arising for elliptic curves of j-invariants 0; 1728 are considered. These curves are known to have priority in pairing-based cryptography. The first task is devoted to the point compression of an elliptic curve, and the second one to the construction of a mapping from a finite field to the point group of an elliptic curve over it. To derive the corresponding explicit formulas, we use rathernon-trivial methods of birational geometry over finite fields, along with the theory of (generalized) Kummer surfaces. In contrast to the already known approaches to solving the mentioned tasks, ours require fewer exponentiations in the base field. This is significant, since in general even one exponentiation is considered a quite time-consuming operation. The thesis also studies a wide class of algebraic geometry (AG) codes on non-split toric surfaces, which we call non-split toric codes. Many of them are contained in a well-known class of q-ary BCH codes that can be quickly decoded (compared with AG ones). On the other hand, the theory of BCH codes (in contrast to AG ones) is not deep enough to exactly estimate their parameters. More precisely, to calculate the minimum distance of some non-split toric BCH codes, we use the theory of elliptic curves over finite fields.; Dans la thèse deux tâches se posant pour des courbes elliptiques de j-invariants 0; 1728 sont considérées. Ces courbes sont connues pour être prioritaires en cryptographie à base de couplages. La première tâche est consacrée à la compression de points d'une courbe elliptique, et la seconde à la construction d'une application d'un corps fini dans le groupe des points d'une courbe elliptique sur lui. Pour dériver les formules explicites correspondantes, nous utilisons des méthodes peu banales de géométrie birationnelle sur des corps finis, ainsi que la théorie des surfaces de Kummer (généralisées). Contrairement aux approches déjà connues pour résoudre les tâches mentionnées, les nôtres nécessitent moins d'exponentiations dans le corps de base. C'est important, car en général, même une seule exponentiation est considérée comme une opération assez longue. La thèse étudie également une large classe de codes (AG) de géométrie algébrique sur des surfaces toriques non déployées que nous appelons codes toriques non déployés. Beaucoup d'entre eux sont contenus dans une classe bien connue de codes BCH q-aires qui peuvent être décodés rapidement (par rapport à ceux AG). En revanche, la théorie des codes BCH (contrairement à ceux AG) n'est pas assez profonde pour estimer exactement leurs paramètres. Plus précisément, pour calculer la distance minimale de certains codes BCH toriques non déployés, nous utilisons la théorie des courbes elliptiques sur des corps finis.

In this thesis, we study the security of symmetric cryptographic primitives. These systems are based on transformations relying on mathematical objects that can be represented in multiple ways. We then exploit different induced structures to highlight new vulnerabilities. By exploiting various representations, we cryptanalyzed some schemes submitted to the CAESAR competition, and also some dedicated and generic stream ciphers. We exhibited design criteria for lightweight block ciphers in view of the NIST standardization process and in the case of stream ciphers we defined new cryptographic criteria more relevant than the usual ones. More precisely, we study the security of lightweight block ciphers with respect to the recent invariant attacks, and we show how to avoid them with an appropriate choice of the linear layer and the round constants. We propose a new cryptanalysis of the filtered registers, by decomposing elements in the multiplicative subgroups of the finite field with 2^n elements. The analysis of the FLIP cipher, but also of the Goldreich pseudo-random generator, revealed weaknesses that are exploitable in ``guess and determine'' attacks. This leads to new criteria on the Boolean functions used in this context. Finally, we cryptanalyze a weaker version of the authenticated encryption scheme Ketje using several techniques, in order to refine the security evaluation of this cipher., Dans cette thèse, nous étudions la sécurité de primitives cryptographiques. Ces systèmes sont fondés sur des transformations utilisant des objets mathématiques représentés de multiples manières. Nous utilisons alors certaines structures inhérentes à leurs composantes, et jusqu'alors non prises en compte, pour mettre en évidence de nouvelles vulnérabilités. Par l'exploitation de diverses représentations, nous avons ainsi cryptanalysé des chiffrements authentifiés de la compétition CAESAR, des chiffrements à flot spécifiques et des constructions génériques. Nous avons donné des critères de conception en vue de la standardisation par le NIST de chiffrements à bas coût. Dans le cas des chiffrements à flot, nous avons défini de nouveaux critères cryptographiques plus pertinents que les critères usuels. Plus précisément, nous analysons la sécurité des chiffrements par bloc légers au regard des récentes attaques par invariant, et nous montrons comment les éviter par un choix approprié de la couche linéaire de diffusion et des constantes de tour. Nous proposons une nouvelle cryptanalyse des registres filtrés, grâce à la décomposition des éléments dans les sous-groupes multiplicatifs du corps fini à 2^n éléments. L'analyse du chiffrement FLIP, mais aussi du générateur pseudo-aléatoire de Goldreich a mis en évidence des faiblesses exploitables dans des attaques de type ``supposer et déterminer'', qui nécessitent la prise en compte de nouveaux critères sur les fonctions booléennes utilisées dans ce contexte. Enfin, nous cryptanalysons une version simplifiée du chiffrement authentifié Ketje en utilisant plusieurs techniques, permettant ainsi d'affiner l'évaluation de sa sécurité.

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); 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); 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

We propose two-sources randomness extractors over finite fields and on elliptic curves that can extract from two sources of information without consideration of other assumptions that the starting algorithmic assumptions with a competitive level of security. These functions have several applications. We propose here a description of a version of a Diffie-Hellman key exchange protocol and key extraction., Nous proposons des extracteurs d'aléas 2-sources sur les corps finis et sur les courbes elliptiques capables d'extraire à partir de plusieurs sources d'informations sans considération d'autres hypothèses que les hypothèses algorithmiques de départ avec un niveau de sécurité compétitif. Ces fonctions possèdent plusieurs applications. Nous proposons ici une version du protocole d'échange de clé Diffie-Hellman incluant la phase d'extraction.

The pairings on elliptic curves were first introduced by André Weil in 1948. They are usedin asymmetric cryptography. They have been very popular over the last decades. The pairingson elliptic curves allow to perform some cryptographic operations which are not easily performedwithout pairings like short signature and the identity based cryptography.Recently, the calculation of pairings has become easier than before thanks to the introduction of newmathematical optimizations on elliptic curves which are called the pairing-friendly elliptic curves.Nowadays, it is important to transferthis technology from theory to practical implementation whichis executed on some electronic components as FPGA or SIM cards.In the first part of this thesis, we studied the problem of pairing implementation in restrictedenvironment. Indeed, the computation of the Tate pairing, or also one of its variants, requiresthe implementation of a many temporary variables. Therefore, it requires a lot of memory of theelectronic component on which we wish to implement such a pairing. In this context, by doingmathematical optimizations, we have saved 37% of the memory in implementing these pairings inrestricted environments.The second problem is the security of the cryptographic protocols based on pairings. Since pairingson elliptic curves are supposed to be physically attacked, we studied these attacks and we proposeda counter measure., Les couplages sont des outils mathématiques introduits par André Weil en 1948. Ils sont unsujet très en vogue depuis une quinzaine d’années en cryptographie asymétrique. Ils permettent eneffet de réaliser des opérations cryptographiques impossible à réaliser simplement autrement.Ces dernières années, le calcul des couplages est devenu plus facile grâce à l’introduction de nouvellesméthodes des calculs mathématiques particulièrement efficaces sur les courbes elliptiquesdites les courbes bien adaptées aux couplages.Aujourd’hui, nous sommes au stade de transfert de cette technologie, de la théorie vers la miseen oeuvre pratique, sur des composants électroniques. Ce transfert soulève de nombreuses problématiquesqui s’avèrent difficile à surmonter à cause de la différence de culture scientifique entremathématiciens et micro-électroniciens.Dans le présent document, en premier lieu, nous avons étudié le problème de l’implémentationdu couplage dans des environnements à mémoire limitée. Dans ce contexte, en faisant des optimisationsmathématiques, nous avons pu implémenté ces couplages dans des environnements retreints,nous avons gagné environ 37% en mémoire.Le deuxième problème que nous avons traité est la sécurité des protocoles cryptographiques baséssur les couplages. Dans ce contexte, nous avons étudié les attaques sur les couplages et nous avonsproposé ue contre-mesure plus efficace que celle présentée dans la littérature.

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., 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 and security market is growing up at an annual rate of 17 % according to some recent studies. Cryptography is known to be the science of secret. It is based on mathematical hard problems as integers factorization, the well-known discrete logarithm problem. Although those problems are trusted, software or hardware implementations of cryptographic algorithms can suffer from inherent weaknesses. Execution time, power consumption (...) can differ depending on secret informations such as the secret key. Because of that, some malicious attacks could be used to exploit these weak points and therefore can be used to break the whole crypto-system. In this thesis, we are interested in protecting our physical device from the so called side channel attacks as well as interested in proposing new GF(2^m) multiplication algorithms used over elliptic curves cryptography. As a protection, we first thought that parallel scalar multiplication (using halve-and-add and double-and-add algorithms both executed at the same time) would be a great countermeasure against template attacks. We showed that it was not the case and that parallelism could not be used as protection by itself : it had to be combined with more conventional countermeasures. We also proposed two new GF(2^m) representations we respectively named permuted normal basis (PNB) and Phi-RNS. Those two representations, under some requirements, can offer a great time-area trade-off on FPGAs., La cryptographie et la problématique de la sécurité informatique deviennent des sujets de plus en plus prépondérants dans un monde hyper connecté et souvent embarqué. La cryptographie est un domaine dont l'objectif principal est de ''protéger'' l'information, de la rendre inintelligible à ceux ou à celles à qui elle n'est pas destinée. La cryptographie repose sur des algorithmes solides qui s'appuient eux-mêmes sur des problèmes mathématiques réputés difficiles (logarithme discret, factorisation des grands nombres etc). Bien qu'il soit complexe, sur papier, d'attaquer ces systèmes de protection, l'implantation matérielle ou logicielle, si elle est négligée (non protégée contre les attaques physiques), peut apporter à des entités malveillantes des renseignements complémentaires (temps d’exécution, consommation d'énergie etc) : on parle de canaux cachés ou de canaux auxiliaires. Nous avons, dans cette thèse, étudié deux aspects. Le premier est l'apport de nouvelles idées algorithmiques pour le calcul dans les corps finis binaires GF(2^m) utilisés dans le cadre de la cryptographie sur courbes elliptiques. Nous avons proposé deux nouvelles représentations des éléments du corps : la base normale permutée et le Phi-RNS. Ces deux nouveautés algorithmiques ont fait l'objet d'implémentations matérielles en FPGA dans laquelle nous montrons que ces premières, sous certaines conditions, apportent un meilleur compromis temps-surface. Le deuxième aspect est la protection d'un crypto-processeur face à une attaque par canaux cachés (dite attaque par «templates»). Nous avons implémenté, en VHDL, un crypto-processeur complet et nous y avons exécuté, en parallèle, des algorithmes de «double-and-add» et «halve-and-add» afin d'accélérer le calcul de la multiplication scalaire et de rendre, de par ce même parallélisme, notre crypto-processeur moins vulnérable face à certaines attaques par canaux auxiliaires. Nous montrons que le parallélisme seul des calculs ne suffira pas et qu'il faudra marier le parallélisme à des méthodes plus conventionnelles pour assurer, à l'implémentation, une sécurité raisonnable.

Cryptography and security market is growing up at an annual rate of 17 % according to some recent studies. Cryptography is known to be the science of secret. It is based on mathematical hard problems as integers factorization, the well-known discrete logarithm problem. Although those problems are trusted, software or hardware implementations of cryptographic algorithms can suffer from inherent weaknesses. Execution time, power consumption (...) can differ depending on secret informations such as the secret key. Because of that, some malicious attacks could be used to exploit these weak points and therefore can be used to break the whole crypto-system. In this thesis, we are interested in protecting our physical device from the so called side channel attacks as well as interested in proposing new GF(2^m) multiplication algorithms used over elliptic curves cryptography. As a protection, we first thought that parallel scalar multiplication (using halve-and-add and double-and-add algorithms both executed at the same time) would be a great countermeasure against template attacks. We showed that it was not the case and that parallelism could not be used as protection by itself : it had to be combined with more conventional countermeasures. We also proposed two new GF(2^m) representations we respectively named permuted normal basis (PNB) and Phi-RNS. Those two representations, under some requirements, can offer a great time-area trade-off on FPGAs.; La cryptographie et la problématique de la sécurité informatique deviennent des sujets de plus en plus prépondérants dans un monde hyper connecté et souvent embarqué. La cryptographie est un domaine dont l'objectif principal est de ''protéger'' l'information, de la rendre inintelligible à ceux ou à celles à qui elle n'est pas destinée. La cryptographie repose sur des algorithmes solides qui s'appuient eux-mêmes sur des problèmes mathématiques réputés difficiles (logarithme discret, factorisation des grands nombres etc). Bien qu'il soit complexe, sur papier, d'attaquer ces systèmes de protection, l'implantation matérielle ou logicielle, si elle est négligée (non protégée contre les attaques physiques), peut apporter à des entités malveillantes des renseignements complémentaires (temps d’exécution, consommation d'énergie etc) : on parle de canaux cachés ou de canaux auxiliaires. Nous avons, dans cette thèse, étudié deux aspects. Le premier est l'apport de nouvelles idées algorithmiques pour le calcul dans les corps finis binaires GF(2^m) utilisés dans le cadre de la cryptographie sur courbes elliptiques. Nous avons proposé deux nouvelles représentations des éléments du corps : la base normale permutée et le Phi-RNS. Ces deux nouveautés algorithmiques ont fait l'objet d'implémentations matérielles en FPGA dans laquelle nous montrons que ces premières, sous certaines conditions, apportent un meilleur compromis temps-surface. Le deuxième aspect est la protection d'un crypto-processeur face à une attaque par canaux cachés (dite attaque par «templates»). Nous avons implémenté, en VHDL, un crypto-processeur complet et nous y avons exécuté, en parallèle, des algorithmes de «double-and-add» et «halve-and-add» afin d'accélérer le calcul de la multiplication scalaire et de rendre, de par ce même parallélisme, notre crypto-processeur moins vulnérable face à certaines attaques par canaux auxiliaires. Nous montrons que le parallélisme seul des calculs ne suffira pas et qu'il faudra marier le parallélisme à des méthodes plus conventionnelles pour assurer, à l'implémentation, une sécurité raisonnable.

National audience; Le LFSR filtré est un modèle de chiffrement à flot à coût réduit, qui est encore actuellement très utilisé dans des systèmes réels soit tout seul soit comme partie d'un générateur plus complexe. De nombreuses attaques existent déjà sur ce type de systèmes comme les attaques par corrélation ou les attaques algébriques. Rønjom et Cid ont constaté que, dans certains cas, les représentations équivalentes des LFSR filtrés obtenues par un changement de racine primitive pouvaient aboutir à un nouveau type de cryptanalyse. Ils ont aussi décrit une attaque qui s'applique quand la fonction de filtrage est une composante d'une fonction monôme x → Tr(λx r) sur le corps fini F 2 n où n est la longueur du LFSR. Beaucoup de questions se posent en conséquence de cet article : la possibilité de généraliser cette attaque à d'autres fonctions de filtrage et la recherche d'autres attaques exploitant ces représentations équivalentes. L'utilisation des représentations équivalentes m'a permis de mettre en évidence trois nouveaux types de faiblesses potentielles pour les LFSR filtrés et ainsi de donner de nouveaux critères à prendre en compte pour ce type de système.

International audience; The construction of cyclic codes can be generalized to so called module $\theta$-cyclic codes using noncommutative polynomials. The product of the generator polynomial $g$ of a self-dual module $\theta$-cyclic code and its "skew reciprocal polynomial" is known to be a noncommutative polynomial of the form $X^n-a$, reducing the problem of the computation of all such codes to a Gröbner basis problem where the unknowns are the coefficients of $g$. In previous work, with the exception of the length $2^s$, over $\FF_4$ a large number of self-dual codes were found. In this paper we show that $a$ must be $\pm 1$ and that for $n=2^s$ the decomposition of $X^n\pm 1$ into a product of $g$ and its "skew reciprocal polynomial" has some rigidity properties which explains the small number of codes found for those particular lengths over $\FF_4$. In order to overcome the complexity limitation resulting from the Gröbner basis computation we present, in the case $\theta$ of order two, an iterative construction of self-dual codes based on least common multiples and factorization of noncommutative polynomials. We use this approach to construct a $[78,39,19]_4$ self-dual code and a $[52,26,17]_9$ self-dual code which improve the best previously known minimal distances for these lengths.

In this thesis we study at length the discrete logarithm problem in finite fields. In the first part, we focus on the notion of smoothness and on ECM, the fastest known smoothness test. We present an improvement to the algorithm by analyzing the Galois properties of the division polynomials. We continue by an application of ECM in the last stage of the number field sieve (NFS). In the second part, we present NFS and its related algorithm on function fields (FFS). We show how to speed up the computation of discrete logarithms in all the prime finite fields of a given bit-size by using a pre-computation. We focus later on the polynomial selection stage of FFS and show how to compare arbitrary polynomials with a unique function. We conclude the second part with an algorithm issued from the recent improvements for discrete logarithm. The key fact was to create a descent procedure which has a quasi-polynomial number of nodes, each requiring a polynomial time. This leads to a quasi-polynomial algorithm for finite fields of small characteristic., Dans cette thèse nous examinons en détail le problème du logarithme discret dans les corps finis. Dans la première partie, nous nous intéressons à la notion de friabilité et à l'algorithme ECM, le plus rapide test de friabilité connu. Nous présentons une amélioration de l'algorithme en analysant les propriétés galoisiennes des polynômes de division. Nous continuons la présentation par une application d'ECM dans la dernière étape du crible algébrique (NFS). Dans la deuxième partie, nous présentons NFS et son algorithme correspondant utilisant les corps de fonctions (FFS). Parmi les améliorations examinées, nous montrons qu'on peut accélérer le calcul de logarithme discret au prix d'un pré-calcul commun pour une plage de premiers ayant le même nombre de bits. Nous nous concentrons ensuite sur la phase de sélection polynomiale de FFS et nous montrons comment comparer des polynômes quelconques à l'aide d'une unique fonction. Nous concluons la deuxième partie avec un algorithme issu des récentes améliorations du calcul de logarithme discret. Le fait marquant est la création d'une procédure de descente qui a un nombre quasi-polynomial de nœuds, chacun exigeant un temps polynomial. Cela a conduit à un algorithme quasi-polynomial pour les corps finis de petite caractéristique.

In this thesis we study at length the discrete logarithm problem in finite fields. In the first part, we focus on the notion of smoothness and on ECM, the fastest known smoothness test. We present an improvement to the algorithm by analyzing the Galois properties of the division polynomials. We continue by an application of ECM in the last stage of the number field sieve (NFS). In the second part, we present NFS and its related algorithm on function fields (FFS). We show how to speed up the computation of discrete logarithms in all the prime finite fields of a given bit-size by using a pre-computation. We focus later on the polynomial selection stage of FFS and show how to compare arbitrary polynomials with a unique function. We conclude the second part with an algorithm issued from the recent improvements for discrete logarithm. The key fact was to create a descent procedure which has a quasi-polynomial number of nodes, each requiring a polynomial time. This leads to a quasi-polynomial algorithm for finite fields of small characteristic, Dans cette thèse nous examinons en détail le problème du logarithme discret dans les corps finis. Dans la première partie, nous nous intéressons à la notion de friabilité et à l'algorithme ECM, le plus rapide test de friabilité connu. Nous présentons une amélioration de l'algorithme en analysant les propriétés galoisiennes des polynômes de division. Nous continuons la présentation par une application d'ECM dans la dernière étape du crible algébrique (NFS). Dans la deuxième partie, nous présentons NFS et son algorithme correspondant utilisant les corps de fonctions (FFS). Parmi les améliorations examinées, nous montrons qu'on peut accélérer le calcul de logarithme discret au prix d'un pré-calcul commun pour une plage de premiers ayant le même nombre de bits. Nous nous concentrons ensuite sur la phase de sélection polynomiale de FFS et nous montrons comment comparer des polynômes quelconques à l'aide d'une unique fonction. Nous concluons la deuxième partie avec un algorithme issu des récentes améliorations du calcul de logarithme discret. Le fait marquant est la création d'une procédure de descente qui a un nombre quasi-polynomial de noeuds, chacun exigeant un temps polynomial. Cela a conduit à un algorithme quasi-polynomial pour les corps finis de petite caractéristique

International audience; Let F a finite field, Q a given element of F[T] with positive degree and k a positive integer. The goal of this work is to study the Q-automaticity of the set of kth powers of elements of F[T] and to calculate the number of polynomials X ∈ F[T] of degree N such that the sum of digits of Xk in base Q is fixed.

Let F a finite field, Q a given element of F[T] with positive degree and k a positive integer. The goal of this work is to study the Q-automaticity of the set of kth powers of elements of F[T] and to calculate the number of polynomials X ∈ F[T] of degree N such that the sum of digits of Xk in base Q is fixed.

The integer factorization and discrete logarithm problems are cornerstones of several public-key cryptography algorithms. In the realm of algorithms targeted at solving these highly difficult challenges, the number field sieve algorithm and its siblings are of utmost importance. Part 1 of this work presents the family of algorithms around the number field sieve, together with several personal contributions in this research area. Other works are detailed in part 2, notably in relationship with the discrete logarithm problem on Jacobians of curves, and my contributions to this problem in some special cases. Some aspects of my contributions on sparse linear algebra in finite fields, motivated by the aforementioned algorithms, are discussed in part 3 of this work. Part 4 covers my research on computer arithmetic, and in particular efficient arithmetic for binary polynomials. Parts 3 and 4 of this work emphasize a strong connection with the goal of efficient implementation.; Le problème de la factorisation et celui du logarithme discret sont deux fondements essentiels de nombreux algorithmes de la cryptographie à clé publique. Dans le champ des algorithmes pour attaquer ces problèmes éminemment ardus, le crible algébrique et ses algorithmes cousins occupent une place de première importance. La première partie de ce mémoire est consacrée à la présentation de la " famille " du crible algébrique, et à plusieurs de mes contributions dans ce domaine. D'autres travaux sont abordés dans la partie suivante, notamment en lien avec le problème du logarithme discret sur les jacobiennes de courbes, et à ma contribution à de nouveaux algorithmes pour ce problème dans certains cas particuliers. La partie 3 du mémoire aborde mes travaux sur le thème de l'algèbre linéaire creuse sur les corps finis, motivés par le contexte d'application des algorithmes précédemment cités. La partie 4, enfin, traite de mes travaux dans le domaine de l'arithmétique, notamment concernant l'arithmétique des polynômes sur GF(2). La proximité des travaux apparaissant dans ces parties 3 et 4 avec des problématiques d'implantation indique le souci permanent, dans mes travaux, de ne pas laisser de côté cet aspect.

Computational complexity is the study of the resources — time, memory, …— needed to algorithmically solve a problem. Within these settings, algebraic complexity theory is the study of the computational complexity of problems of algebraic nature, concerning polynomials. In this thesis, we study several aspects of algebraic complexity. On the one hand, we are interested in the expressiveness of the determinants of matrices as representations of polynomials in Valiant's model of complexity. We show that symmetric matrices have the same expressiveness as the ordinary matrices as soon as the characteristic of the underlying field in different from two, but that this is not the case anymore in characteristic two. We also build the smallest known representation of the permanent by a determinant.On the other hand, we study the computational complexity of algebraic problems. We show that the detection of roots in a system of n homogeneous polynomials in n variables in NP-hard. In line with the “VP = VNP ?”question, which is the algebraic version of “P = NP?” we obtain a lower bound for the computation of the permanent of a matrix by an arithmetic circuit, and we point out the links between this problem and the polynomial identity testing problem. Finally, we give efficient algorithms for the factorization of lacunary bivariate polynomials.; 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.

Computational complexity is the study of the resources — time, memory, …— needed to algorithmically solve a problem. Within these settings, algebraic complexity theory is the study of the computational complexity of problems of algebraic nature, concerning polynomials. In this thesis, we study several aspects of algebraic complexity. On the one hand, we are interested in the expressiveness of the determinants of matrices as representations of polynomials in Valiant's model of complexity. We show that symmetric matrices have the same expressiveness as the ordinary matrices as soon as the characteristic of the underlying field in different from two, but that this is not the case anymore in characteristic two. We also build the smallest known representation of the permanent by a determinant.On the other hand, we study the computational complexity of algebraic problems. We show that the detection of roots in a system of n homogeneous polynomials in n variables in NP-hard. In line with the “VP = VNP ?”question, which is the algebraic version of “P = NP?” we obtain a lower bound for the computation of the permanent of a matrix by an arithmetic circuit, and we point out the links between this problem and the polynomial identity testing problem. Finally, we give efficient algorithms for the factorization of lacunary bivariate polynomials., 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.

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, the 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 completely 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 characterization 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 characterized 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 the FPGA based test platform that we have designed is provided.; 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 paper aims to provide an overview of recent researches studies on Camille Jordan's early works (1860-1870). We especially shed new light on the relation between Galois and Jordan by discussing the collective dimensions of Jordan's works and their receptions.; Cet article propose une synthèse de travaux de recherches récents. Il vise à donne un panorama des premiers travaux de Camille Jordan sur la période séparant la thèse de ce dernier en 1860 et la publication en 1870 du célèbre Traité des substitutions algébriques. En s'appuyant sur quatre annexes, l'article discute en particulier de la relation entre les travaux de Galois et ceux de Jordan et offre de nouvelles perspectives sur les dimensions collectives de ces derniers et leurs réceptions.

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, the 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 completely 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 characterization 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 characterized 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 the FPGA based test platform that we have designed is provided., 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.

In this thesis we apply techniques from computer algebra and language theory to speed up the elementary operations in some specific towers of finite fields. We apply our construction to the problem of computing isogenies between elliptic curves and obtain faster (both asymptotically and in practice) variants of Couveignes' algorithm. The document is divided in four parts. In Part I we recall some basic notions from algebra and complexity theory. Part II deals with the transposition principle: in it we generalize ideas of Bostan, Schost and Lecerf, and show that it is possible to automatically transpose computer programs without losses in time complexity and with a small loss in space complexity. Part III combines the results on the transposition principle with classical techniques from elimination theory; we apply these ideas to obtain asymptotically optimal algorithms for the arithmetic of Artin-Schreier towers of finite fields. We also describe an implementations of these algorithms. Finally, in Part IV we use the previous results to speed up Couveignes' algorithm and compare the result with the other state of the art algorithms for isogeny computation. We also present a new generalization of Couveignes' algorithm that computes isogenies of unknown degree.; 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.

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)., 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

Scientific computing is often associated with numerical computation. Yet in many scientific disciplines it is necessary to go beyond the approximations: need for certification of results, computation over discrete mathematical structures, numerical algorithm instability. Computer algebra therefore strive to give accurate or certified results. Now, the main obstruction to the use of symbolic computation is often the poor performance of commercial systems even on fundamental operations such as linear algebra. The goal of this work is to reduce the gap between exact and numerical computations, both in the algorithm and the software sides. The challenges are numerous: developing an effective arithmetic for discrete structures; designing algorithms with optimal leading terms of complexity, taking into account the growth of intermediate data; transcribing these algorithms in software that combines perennial efficiency, interfacing and genericity.; Le calcul scientifique est souvent associé au calcul numérique. Pourtant dans de nombreuses disciplines scientifiques il est nécessaire d'aller au-delà du calcul approché : nécessité de certification des résultats, calculs dans des structures mathématiques discrètes, instabilité des algorithmique numériques. Le calcul exact s'attache donc à donner des résultats exacts ou certifiés. Cependant, la principale obstruction à l'utilisation du Calcul Formel est bien souvent les faibles performances des systèmes commerciaux y compris pour les opérations fondamentales comme l'algèbre linéaire. L'objectif de ces travaux est donc de réduire l'écart entre le calcul exact et le calcul numérique, tant sur le plan algorithmique, que sur le plan logiciel. Les défis sont multiples : développer une arithmétique efficace dans les structures discrètes ; concevoir des algorithmes ayant un terme dominant de complexité optimal même en tenant compte de la croissance des données intermédiaires ; transcrire ces algorithmes dans des logiciels combinant efficacité pérenne, interfaçage et généricité.

International audience; We construct two new families of basis for finite field extensions. Basis in the first family, the so-called elliptic basis, are not quite normal basis, but they allow very fast Frobenius exponentiation while preserving sparse multiplication formulas. Basis in the second family, the so-called normal elliptic basis are normal basis and allow fast (quasi linear) arithmetic. We prove that all extensions admit models of this kind.

The theory of algebraic-geometric codes has been developed in the beginning of the 80's after an article of V.D. Goppa. Given a smooth projective algebraic curve X over a finite field, there are two different constructions of error-correcting codes. The first one, called "functional", uses some rational functions on X and the second one, called "differential", involves some rational 1-forms on this curve. Hundreds of papers are devoted to the study of such codes. In addition, a generalization of the functional construction for algebraic varieties of arbitrary dimension is given by Y. Manin in an article published in 1984. A few papers about such codes has been published, but nothing has been done concerning a generalization of the differential construction to the higher-dimensional case. In this thesis, we propose a differential construction of codes on algebraic surfaces. Afterwards, we study the properties of these codes and particularly their relations with functional codes. A pretty surprising fact is that a main difference with the case of curves appears. Indeed, if in the case of curves, a differential code is always the orthogonal of a functional one, this assertion generally fails for surfaces. Last observation motivates the study of codes which are the orthogonal of some functional code on a surface. Some formulas for the estimation of the minimal distance of such codes are given using some properties of linear systems on a variety. Therefore, we prove that, under some condition on the surface, these codes can be realized as sums of differential codes. Moreover, we show that some answers to some open problems "à la Bertini" could give very interesting informations on the parameters of these codes.; La théorie des codes géométriques s'est développée au début des années 80 sur l'impulsion d'un article de V.D. Goppa publié en 1981. Etant donnée une courbe algébrique projective lisse X sur un corps fini, on dispose de deux constructions de codes correcteurs d'erreurs. Une construction dite fonctionnelle qui fait intervenir certaines fonctions rationnelles sur X et une construction différentielle qui fait appel à certaines 1-formes différentielles rationnelles sur X . L'étude de ces codes construits sur des courbes a donné lieu à la publication de plusieurs centaines d'articles. Parallèlement à ces travaux, une généralisation de la construction fonctionnelle à des variétés algébriques de dimension quelconque est proposée par Y. Manin dans un article publié en 1984. On dénombre quelques dizaines de travaux publiés portant sur l'étude de tels codes. Cependant, aucun développement n'a été effectué dans le sens d'une généralisation de la construction différentielle. Dans cette thèse nous proposons une construction différentielle de codes sur des surfaces algébriques. Nous étudions ensuite les propriétés de ces codes et plus particulièrement leurs relations avec les codes fonctionnels. De façon un peu surprenante, on observe l'apparition d'une différence majeure avec le cas des courbes. En effet, si sur une courbe l'orthogonal d'un code fonctionnel est différentiel, ce fait est en général faux sur une surface. Ce résultat motive l'étude des orthogonaux de codes fonctionnels. Des formules pour l'estimation de la distance minimale de tels codes sont données en utilisant des propriétés de systèmes linéaires sur une variété. On montre également que, sous certaines conditions sur la surface, ces codes sont somme de codes différentiels et que des réponses à certains problèmes ouverts de géométrie algébrique "à la Bertini" fourniraient des informations supplémentaires sur les paramètres de ces codes.

National audience

For a few decades, numerical linear algebra has seen intensive developments in both mathematical and computer science theory which have led to genuine standard software like BLAS or LAPACK.In computer algebra the situation has not advanced as much, in particular because of the diversity of the problems and because of much of the theoretical progress have been done recently.This thesis falls into a recent class of work which aims at uniforming high-performance codes from many specialized libraries into a single platform of computation. In particular, the emergence of robust and portable libraries like GMP or NTL for exact computationhas turned out to be a real asset for the development of applications in exact linear algebra.In this thesis, we study the feasibility and the relevance of the re-use of specialized codes to develop a high performance exact linear algebra library, namely the LinBox library. We use the generic programming mechanisms of C++ (abstract class, template class) to provide an abstraction of the mathematical objects and thus to allow the plugin of external components. Our objective is then to design and validate, in LinBox, high level generic toolboxes for the implementation of algorithms in exact linear algebra.In particular, we propose "exact/numeric" hybrid computation routines for dense matrices over finite fields which nearly match with the performance obtained by numerical libraries like LAPACK.On a higher level, we reuse these hybrid routines to solve very efficiently a classical problem of computer algebra: solving diophantine linear systems.Hence, this allowed us to validate the principle of code reuse in LinBox library and more generally in computer algebra.The LinBox library is available at www.linalg.org.; L'algèbre linéaire numérique a connu depuis quelques décennies des développements intensifs autant au niveau mathématique qu'informatique qui ont permis d'aboutir à de véritable standard logiciel comme BLAS ou LAPACK.Dans le cadre du calcul exact ou formel, la situation n'est pas aussi avancée, en particulierà cause de la diversité des problématiques et de la jeunesse des progrès théoriques.Cette thèse s'inscrit dans une tendance récente qui vise à fédérer des codes performantsprovenant de bibliothèques spécialisées au sein d'une unique plateforme de calcul.En particulier, l'émergence de bibliothèques robustes et portables comme GMP ou NTL pour le calcul exact s'avére être un réel atout pour le développement d'applications en algèbre linéaire exacte.Dans cette thèse, nous étudions la faisabilité et la pertinence de la réutilisation de codes spécialisés pour développer une bibliothèque d'algèbre linéaire exacte performante, à savoir la bibliothèque LinBox.Nous nous appuyons sur les mécanismes C++ de programmation générique (classes abtraites, classes templates) pour fournir une abstraction des composantes mathématiques et ainsi permettre le plugin de composants externes.Notre objectif est alors de concevoir et de valider des boîtes à outils génériques haut niveau dans LinBox pour l'implantation d'algorithmes en algèbre linéaire exacte. 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.À un plus haut niveau, ces routines nous permettent de valider la réutilisation de codes spécifiques sur un problème classique du calcul formel: la résolution de systèmes linéaires diophantiens.La bibliothèque LinBox est disponible à www.linalg.org.

The core of this thesis is the structure of Drinfeld Modules. This notion was introduced by Drinfeld in 1973, as "elleptic modules". These algebraic objects are the analog of elleptic curves on both of the field of numbers and the finite fields, given by the reduction modulo non-archimedian place. The arithmetical study of such objets becomes legitim, motivated by the arithmeticsofthecurvesdefinedonafinite fields and initiated by Artin, Hasse and Weil. In this direction, we extend this analogy for Drinfeld modules of rank two, in fact we give one analog of Weil theorem, Deuring-Waterhouse theorem, and the work of S.Vladut for the cyclicity of such algebraic structure., La notion de modules de Drinfeld est le centre de cette thèse, cette notion fut introduite par Drinfeld en 1973, comme étant des " modules elliptiques" appelés de nos jours modules de Drinfeld. Ceux sont des objets algèbriques analogues aux courbes elliptiques sur les corps des nombres et sur les corps finis, obtenus par la réduction modulo une place non-archimédiennene. Une étude de l'arithmétique de tels objet devient légitime, motivée par l'arithmétique des courbes définies sur un corps fini initiée par Artin, Hasse et Weil. Dans cette direction on pousse cette analogie, pour un module de Drinfeld de rang 2, à la majorité de points étudiés pour des courbes elliptiques sur un corps fini. On donne plus précisement un analogue du théorème de Weil, théorème de Deuring-Waterhouse, et un analogue du travail de S. Vladut sur la cyclicité de tel structure algébrique.

The core of this thesis is the structure of Drinfeld Modules. This notion was introduced by Drinfeld in 1973, as "elleptic modules". These algebraic objects are the analog of elleptic curves on both of the field of numbers and the finite fields, given by the reduction modulo non-archimedian place. The arithmetical study of such objets becomes legitim, motivated by the arithmeticsofthecurvesdefinedonafinite fields and initiated by Artin, Hasse and Weil. In this direction, we extend this analogy for Drinfeld modules of rank two, in fact we give one analog of Weil theorem, Deuring-Waterhouse theorem, and the work of S.Vladut for the cyclicity of such algebraic structure., La notion de modules de Drinfeld est le centre de cette thèse, cette notion fut introduite par Drinfeld en 1973, comme étant des " modules elliptiques" appelés de nos jours modules de Drinfeld. Ceux sont des objets algèbriques analogues aux courbes elliptiques sur les corps des nombres et sur les corps finis, obtenus par la réduction modulo une place non-archimédiennene. Une étude de l'arithmétique de tels objet devient légitime, motivée par l'arithmétique des courbes définies sur un corps fini initiée par Artin, Hasse et Weil. Dans cette direction on pousse cette analogie, pour un module de Drinfeld de rang 2, à la majorité de points étudiés pour des courbes elliptiques sur un corps fini. On donne plus précisement un analogue du théorème de Weil, théorème de Deuring-Waterhouse, et un analogue du travail de S. Vladut sur la cyclicité de tel structure algébrique.

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.

International audience

The main idea of the ``black box'' approach in exact linear algebra is to reduce matrix problems to the computation of minimum polynomials. In most cases preconditioning is necessary to obtain the desired result. Here, good preconditioners will be used to ensure geometrical / algebraic properties on matrices, rather than numerical ones, so we do not address a condition number. We offer a review of problems for which (algebraic) preconditioning is used, provide a bestiary of preconditioning problems, and discuss several preconditioner types to solve these problems. We include new conditioners, new analyses of preconditioner performance, and results on the relations among preconditioning problems and with linear algebra problems. Thus improvements are offered for the efficiency and applicability of preconditioners. The focus is on linear algebra problems over finite fields, but most results are valid for entries from arbitrary fields.; L'idée principale de l’approche à base de boîtes noires en algèbre linéaire exacte est de ramener la réquisition de problèmes matriciels à des calculs de polynômes minimaux. Dans le plupart des cas, un préconditionnement s'avère nécessaire pour obtenir le résultat désiré. nous parlerons de "bons" préconditionnements quand il s'agira d'assurer des propriétés géométriques et algébriques sur les matrices plutôt que des qualités numériques, donc sans relation avec un nombre de conditionnement. dans ce rapport nous passons en revue divers problèmes pour lesquels on utilise un préconditionnement (algébrique), proposons une classification des différents problèmes de préconditionnement et étudions plusieurs solutions. En particulier, nous envisageons de nouveaux préconditionnements, de nouvelles analyses de leurs performances et des relations pouvant être définies entre eux en rapport avec les questions d'algèbre linéaire qu'ils résolvent. Des améliorations sont donc obtenues quant à l’efficacité et l’applicabilité des préconditionnements. Ces résultats se concentrent sur des matrices à coefficients dans des corps finis mais ils s'appliquent dans le cas de corps commutatifs quelconques

In every field of scientific and industrial research, the extension of the use of computer science has resulted in an increasing need for computing power. It is thus vital to use these computing resources in parallel. In this thesis we seek to compute the canonical form of very large sparse matrices with integer coefficients, the Smith normal form. By "very large", we mean a million indeterminates and a million equations, i.e. thousand billion of variables. Nowadays, such systems are usually not even storable. However, we are interested in systems for which many of these variables are identical and zero; in this case we talk about sparse systems. We want to solve these systems in an exact way, i.e. we work with integers or in smaller algebraic structures where all the basic arithmetic operations are still valid, finite fields. The rebuilding of the whole solution from the smaller solutions is then relatively easy.; Depuis quelques années, l'extension de l'utilisation de l'informatique dans tous les domaines de recherche scientifique et technique se traduit par un besoin croissant de puissance de calcul. Il est donc vital d'employer les microprocesseurs en parallèle. Le problème principal que nous cherchons à résoudre dans cette thèse est le calcul d'une forme canonique de très grandes matrices creuses à coefficients entiers, la forme normale de Smith. Par "très grandes", nous entendons un million d'inconnues et un million d'équations, c'est-à-dire mille milliards de variables. De tels systèmes sont même, en général, impossibles à stocker actuellement. Cependant, nous nous intéressons à des systèmes dans lesquels beaucoup de ces variables sont identiques et valent zéro; on parle dans ce cas de système creux. Enfin, nous voulons résoudre ces systèmes de manière exacte, c'est-à-dire que nous travaillons avec des nombres entiers ou dans une structure algébrique plus petite et autorisant toutes les opérations classiques, un corps fini. La reconstruction de la solution entière à partir des solutions plus petites est ensuite relativement aisée.

In every field of scientific and industrial research, the extension of the use of computer science has resulted in an increasing need for computing power. It is thus vital to use these computing resources in parallel. In this thesis we seek to compute the canonical form of very large sparse matrices with integer coefficients, the Smith normal form. By "very large", we mean a million indeterminates and a million equations, i.e. thousand billion of variables. Nowadays, such systems are usually not even storable. However, we are interested in systems for which many of these variables are identical and zero; in this case we talk about sparse systems. We want to solve these systems in an exact way, i.e. we work with integers or in smaller algebraic structures where all the basic arithmetic operations are still valid, finite fields. The rebuilding of the whole solution from the smaller solutions is then relatively easy.; Depuis quelques années, l'extension de l'utilisation de l'informatique dans tous les domaines de recherche scientifique et technique se traduit par un besoin croissant de puissance de calcul. Il est donc vital d'employer les microprocesseurs en parallèle. Le problème principal que nous cherchons à résoudre dans cette thèse est le calcul d'une forme canonique de très grandes matrices creuses à coefficients entiers, la forme normale de Smith. Par "très grandes", nous entendons un million d'inconnues et un million d'équations, c'est-à-dire mille milliards de variables. De tels systèmes sont même, en général, impossibles à stocker actuellement. Cependant, nous nous intéressons à des systèmes dans lesquels beaucoup de ces variables sont identiques et valent zéro; on parle dans ce cas de système creux. Enfin, nous voulons résoudre ces systèmes de manière exacte, c'est-à-dire que nous travaillons avec des nombres entiers ou dans une structure algébrique plus petite et autorisant toutes les opérations classiques, un corps fini. La reconstruction de la solution entière à partir des solutions plus petites est ensuite relativement aisée.

In every field of scientific and industrial research, the extension of the use of computer science has resulted in an increasing need for computing power. It is thus vital to use these computing resources in parallel. In this thesis we seek to compute the canonical form of very large sparse matrices with integer coefficients, the Smith normal form. By "very large", we mean a million indeterminates and a million equations, i.e. thousand billion of variables. Nowadays, such systems are usually not even storable. However, we are interested in systems for which many of these variables are identical and zero; in this case we talk about sparse systems. We want to solve these systems in an exact way, i.e. we work with integers or in smaller algebraic structures where all the basic arithmetic operations are still valid, finite fields. The rebuilding of the whole solution from the smaller solutions is then relatively easy.; Depuis quelques années, l'extension de l'utilisation de l'informatique dans tous les domaines de recherche scientifique et technique se traduit par un besoin croissant de puissance de calcul. Il est donc vital d'employer les microprocesseurs en parallèle. Le problème principal que nous cherchons à résoudre dans cette thèse est le calcul d'une forme canonique de très grandes matrices creuses à coefficients entiers, la forme normale de Smith. Par "très grandes", nous entendons un million d'inconnues et un million d'équations, c'est-à-dire mille milliards de variables. De tels systèmes sont même, en général, impossibles à stocker actuellement. Cependant, nous nous intéressons à des systèmes dans lesquels beaucoup de ces variables sont identiques et valent zéro; on parle dans ce cas de système creux. Enfin, nous voulons résoudre ces systèmes de manière exacte, c'est-à-dire que nous travaillons avec des nombres entiers ou dans une structure algébrique plus petite et autorisant toutes les opérations classiques, un corps fini. La reconstruction de la solution entière à partir des solutions plus petites est ensuite relativement aisée.

Minimum weight codewords of cyclic error-correcting codes are considered here. The elementary symmetric functions and the power-sum symmetric functions of the locators of these codewords are related by the Newton's identities. In the first chapter, they are viewed as a system of algebraic equations, whose solutions are studied by means of the Fourier transform. In chapter II, the link with cyclic error-correcting codes is established. On some examples, it is shown how to study the minimum weight codewords on the data of a Grobner basis of the ideal generated by the Newton's identities. In chapter III, the Newton's identities are considered from a theoretical point of view, and results about minimum weight codewords of a family of BCH codes are obtained. These computations occurs in the context of finite fields. In chapter IV, an algorithm is constructed for computing a normal basis of a finite field. A point of view from linear algebra is chosen, and other problems are dealt with (the computation of the minimal polynomial, of the Frobenius form of a matrix, when the factorization of the characteristic polynomial is known).; Nous étudions les mots de poids minimal des codes correcteurs d'erreurs cycliques. Les fonctions symétriques élémentaires et les fonctions puissances des localisateurs de ces mots vérifient les identités de Newton. Dans le premier chapitre celles-ci sont étudiées comme un système d'équations algébriques, dont les solutions sont étudiées par transformation de Fourier. Dans le chapitre II, le lien est fait avec les codes correcteurs d'erreurs cycliques. Sur quelques exemples, il est montré comment étudier les mots de poids minimal sur la donnée d'une base standard de l'idéal engendré par les équations de Newton. Dans le chapitre III, les relations de Newton sont utilisées d'un point de vue théorique, et des résultats sur les mots de poids minimal de certains codes BCH sont obtenus. Ces calculs se placent dans le contexte de la théorie des corps finis. Dans le chapitre IV, un algorithme est développé pour calculer une base normale sur un corps fini. Un point de vue d'algèbre linéaire est choisi, et d'autres problèmes sont abordés (calcul du polynôme minimal, de la forme de Frobenius d'une matrice, lorsque la factorisation du polynôme caractéristique est connue).

Minimum weight codewords of cyclic error-correcting codes are considered here. The elementary symmetric functions and the power-sum symmetric functions of the locators of these codewords are related by the Newton's identities. In the first chapter, they are viewed as a system of algebraic equations, whose solutions are studied by means of the Fourier transform. In chapter II, the link with cyclic error-correcting codes is established. On some examples, it is shown how to study the minimum weight codewords on the data of a Grobner basis of the ideal generated by the Newton's identities. In chapter III, the Newton's identities are considered from a theoretical point of view, and results about minimum weight codewords of a family of BCH codes are obtained. These computations occurs in the context of finite fields. In chapter IV, an algorithm is constructed for computing a normal basis of a finite field. A point of view from linear algebra is chosen, and other problems are dealt with (the computation of the minimal polynomial, of the Frobenius form of a matrix, when the factorization of the characteristic polynomial is known).; Nous étudions les mots de poids minimal des codes correcteurs d'erreurs cycliques. Les fonctions symétriques élémentaires et les fonctions puissances des localisateurs de ces mots vérifient les identités de Newton. Dans le premier chapitre celles-ci sont étudiées comme un système d'équations algébriques, dont les solutions sont étudiées par transformation de Fourier. Dans le chapitre II, le lien est fait avec les codes correcteurs d'erreurs cycliques. Sur quelques exemples, il est montré comment étudier les mots de poids minimal sur la donnée d'une base standard de l'idéal engendré par les équations de Newton. Dans le chapitre III, les relations de Newton sont utilisées d'un point de vue théorique, et des résultats sur les mots de poids minimal de certains codes BCH sont obtenus. Ces calculs se placent dans le contexte de la théorie des corps finis. Dans le chapitre IV, un algorithme est développé pour calculer une base normale sur un corps fini. Un point de vue d'algèbre linéaire est choisi, et d'autres problèmes sont abordés (calcul du polynôme minimal, de la forme de Frobenius d'une matrice, lorsque la factorisation du polynôme caractéristique est connue).

Scientific computing is often associated with numerical computation. Yet in many scientific disciplines it is necessary to go beyond the approximations: need for certification of results, computation over discrete mathematical structures, numerical algorithm instability. Computer algebra therefore strive to give accurate or certified results. Now, the main obstruction to the use of symbolic computation is often the poor performance of commercial systems even on fundamental operations such as linear algebra. The goal of this work is to reduce the gap between exact and numerical computations, both in the algorithm and the software sides. The challenges are numerous: developing an effective arithmetic for discrete structures; designing algorithms with optimal leading terms of complexity, taking into account the growth of intermediate data; transcribing these algorithms in software that combines perennial efficiency, interfacing and genericity.; Le calcul scientifique est souvent associé au calcul numérique. Pourtant dans de nombreuses disciplines scientifiques il est nécessaire d'aller au-delà du calcul approché : nécessité de certification des résultats, calculs dans des structures mathématiques discrètes, instabilité des algorithmique numériques. Le calcul exact s'attache donc à donner des résultats exacts ou certifiés. Cependant, la principale obstruction à l'utilisation du Calcul Formel est bien souvent les faibles performances des systèmes commerciaux y compris pour les opérations fondamentales comme l'algèbre linéaire. L'objectif de ces travaux est donc de réduire l'écart entre le calcul exact et le calcul numérique, tant sur le plan algorithmique, que sur le plan logiciel. Les défis sont multiples : développer une arithmétique efficace dans les structures discrètes ; concevoir des algorithmes ayant un terme dominant de complexité optimal même en tenant compte de la croissance des données intermédiaires ; transcrire ces algorithmes dans des logiciels combinant efficacité pérenne, interfaçage et généricité.

The integer factorization and discrete logarithm problems are cornerstones of several public-key cryptography algorithms. In the realm of algorithms targeted at solving these highly difficult challenges, the number field sieve algorithm and its siblings are of utmost importance. Part 1 of this work presents the family of algorithms around the number field sieve, together with several personal contributions in this research area. Other works are detailed in part 2, notably in relationship with the discrete logarithm problem on Jacobians of curves, and my contributions to this problem in some special cases. Some aspects of my contributions on sparse linear algebra in finite fields, motivated by the aforementioned algorithms, are discussed in part 3 of this work. Part 4 covers my research on computer arithmetic, and in particular efficient arithmetic for binary polynomials. Parts 3 and 4 of this work emphasize a strong connection with the goal of efficient implementation.; Le problème de la factorisation et celui du logarithme discret sont deux fondements essentiels de nombreux algorithmes de la cryptographie à clé publique. Dans le champ des algorithmes pour attaquer ces problèmes éminemment ardus, le crible algébrique et ses algorithmes cousins occupent une place de première importance. La première partie de ce mémoire est consacrée à la présentation de la " famille " du crible algébrique, et à plusieurs de mes contributions dans ce domaine. D'autres travaux sont abordés dans la partie suivante, notamment en lien avec le problème du logarithme discret sur les jacobiennes de courbes, et à ma contribution à de nouveaux algorithmes pour ce problème dans certains cas particuliers. La partie 3 du mémoire aborde mes travaux sur le thème de l'algèbre linéaire creuse sur les corps finis, motivés par le contexte d'application des algorithmes précédemment cités. La partie 4, enfin, traite de mes travaux dans le domaine de l'arithmétique, notamment concernant l'arithmétique des polynômes sur GF(2). La proximité des travaux apparaissant dans ces parties 3 et 4 avec des problématiques d'implantation indique le souci permanent, dans mes travaux, de ne pas laisser de côté cet aspect.