Search

Les codes correcteurs d’effacements sont aujourd’hui une solution bien connue utilisée pour fiabiliser les protocoles de communication ou le stockage distribué des données. La plupart de ces codes sont basés sur l’arithmétique des corps finis, définissant l’addition et la multiplication sur un ensemble fini d’éléments, nécessitant souvent des opérations complexes à réaliser. En raison de besoins en performance toujours plus importants, ces codes ont fait l’objet de nombreuses recherches dans le but d’obtenir de meilleures vitesses d’exécution, tout en ayant la meilleure capacité de correction possible. Nous proposons une méthode permettant de transformer les éléments de certains corps finis en éléments d’un anneau afin d’y effectuer toutes les opérations dans le but de simplifier à la fois le processus de codage et de décodage des codes correcteurs d’effacements, sans aucun compromis sur les capacités de correction. Nous présentons également une technique de réordonnancement des opérations, permettant de réduire davantage le nombre d’opérations nécessaires au codage grâce à certaines propriétés propres aux anneaux utilisés. Enfin, nous analysons les performances de cette méthode sur plusieurs architectures matérielles, et détaillons une implémentation simple, basée uniquement sur des instructions xor et s’adaptant beaucoup plus efficacement que les autres implémentations à un environnement d’exécution massivement parallèle. Erasure codes are widely used to cope with failures for nearly all of today’s networks communications and storage systems. Most of these codes are based on finite field arithmetic, defining the addition and the multiplication over a set of finite elements. These operations can be very complex to perform. As a matter of fact, codes performance improvements are still an up to date topic considering the current data growth explosion. We propose a method to transform the elements of some finite fields into ring elements and perform the operations in this ring to simplify both coding and decoding of erasure codes, without any threshold on the correction capacities.We also present a scheduling technique allowing to reduce the number of operations thanks to some particular properties of the ring structure. Finally, we analyse the performance of such a method considering several hardware architectures and detail a simple implementation, using only xor operations, fully scalable over a multicore environment.

L'objectif de ce mémoire est de dénombrer les polynômes irréductibles unitaires sur un corps fini en prescrivant des contraintes sur les coefficients. Dans les prochaines pages, il sera question de fixer simplement des coefficients, ou simplement de fixer leur signe, leur cubicité ou leur quarticité., The objective of this thesis is to count monic irreducible polnomials over a finite field under some conditions on the coefficients of the polynomial. These conditions will be simply to fix some coefficients, or to fix their sign, cubicity or quarticity.

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.

Le but de ce mémoire est de dénombrer les polynômes irréductibles unitaires dans les corps finis avec certaines conditions sur les coefficients. Notre première condition sera de fixer la trace du polynôme. Par la suite, nous choisirons la cotrace lorsque la trace sera déjà fixée à zéro. Finalement, nous discuterons du cas où la trace et le terme constant sont fixés en même temps., The objective of this thesis is to count the monic irreducible polynomial over finite field with some conditions related to coefficient. First, we will determine the trace of the polynomial. Thereafter, we will elect the cotrace when the trace is already fixed to zero. Finally, we will discuss the case where the trace and the constant term are fixed at the same time

Pour $K$ un corps global (corps de nombres ou corps de fonctions d'une variable sur un corps fini $F$), on dispose de th\'eor\`emes de dualit\'e classiques (Tate, Poitou, Nakayama) pour la cohomologie galoisienne \`a valeurs dans des tores et des modules ab\'eliens finis. Nous \'etablissons de tels th\'eor\`emes pour $K$ le corps des fonctions d'une courbe projective et lisse sur le corps $F={\bf C}((t))$ des s\'eries formelles en une variable sur le corps des complexes. Cela permet de contr\^oler le d\'efaut du principe de Hasse et l'approximation faible pour les espaces homog\`enes sous un tore. Il y a ici des diff\'erences avec le cas classique ($K$ corps global), et aussi avec le cas r\'ecemment \'etudi\'e o\`u $K$ est un corps de fonctions d'une variable sur un corps $p$-adique. Par exemple, la $K$-rationalit\'e d'un tore n'implique pas ici la validit\'e du principe de Hasse pour ses espaces principaux homog\`enes. ---------------- Over a global field $K$ (number field, or function field of a curve over a finite field $F$), arithmetic duality theorems for the Galois cohomology of tori and finite Galois modules have long been known. More recent work investigates the case where $K$ is the function fields of of a curve over a $p$-adic field. For $K$ the function field of a curve over the formal series field $F={\bf C}((t))$, we establish analogous duality theorems. We thus control the obstruction to the local-global principle and to weak approximation for homogeneous spaces of tori. There are differences with the afore described cases. For example the Hasse principle need not hold for principal homogeneous spaces of a $K$-rational torus., Comment: 60 pages, in French

We give lower bounds for the number of effective divisors of degree $\leq g-1$ of an algebraic function field of one variable of genus $g\geq 2$ defined over a finite field. We deduce lower bounds for the class number,depending mainly on the number of places of a certain degree, which improve the best known lower bounds in many cases. Moreover, we prove that any family of algebraic function fields having asymptotically (with respect to the genus) a large number of places of a certain degree $r\geq1$, have a large asymptotical class number for which we give an estimate., On donne des minorations du nombre de diviseurs effectifs de degr\'e $\leq g-1$ d'un corps de fonctions alg\'ebriques en une variable de genre $g\geq 2$ d\'efini sur un corps fini ${\mathbb{F}}_q$. On en d\'eduit alors des minorations du nombre de classes, d\'ependant essentiellement du nombre de places d'un certain degr\'e $r$, qui am\'eliorent les meilleures bornes inf\'erieures connues dans de nombreux cas. De plus, nous montrons que toutes les familles de corps de fonctions alg\'ebriques en une variable ayant asymptotiquement (relativement au genre) un grand nombre de places d'un certain degré $r\geq1$, possèdent un nombre de classe asymptotiquement grand dont nous donnons une estimation.

21 pages; Let $\wh K$ be the field of formal Laurent series in $X^{-1}$ over the finite field $k$, and let $A$ be the ring of polynomials in $X$ over $k$. One of the main results of the paper is to give a particularly nice coding of the geodesic flow on the quotient of the Bruhat-Tits tree $\TT$ of ${\rm PGL}_2(\wh K)$ by ${\rm PGL}_2(A)$, by using the continued fraction expansion of the endpoints of the geodesic lines in $\TT$ (the space of ends of $\TT$ identifies with $\PP_1(\wh K)$). This allows in particular to prove in a dynamical way the invariance of the Haar measure by the Artin map.

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.