L'arithmétique des ordinateurs est une branche de l'informatique qui traite des systèmes de représentation des nombres, des algorithmes arithmétiques et de leurs implantations matérielles ou logicielles. Cette thèse porte sur l'étude et l'implantation matérielle d'opérateurs pour l'évaluation de fonctions en traitement du signal et des images. Sont présentés successivement un générateur d'opérateurs optimisés pour la division, des études portant sur un algorithme d'évaluation de fonctions au moyen d'approximations par fractions rationnelles, et des opérateurs d'évaluation de fonctions basés sur des approximations polynomiales qui demandent peu de matériel. Les différents opérateurs proposés dans cette thèse ont tous été validés sur des circuits FPGA.

Les couplages sont des primitives cryptographiques qui interviennent désormais dans de nombreux protocoles. Dès lors, il est nécessaire de s'intéresser à leur calcul et à leur implémentation efficace. Pour ce faire, nous nous reposons sur une étude algorithmique et arithmétique de ces fonctions mathématiques. Les couplages sont des applications bilinéaires définies sur des courbes algébriques, plus particulièrement, dans le cas qui nous intéresse, des courbes elliptiques et hyperelliptiques. Nous avons choisi de nous concentrer sur une sous-famille de celles-ci : les courbes supersingulières dont les propriétés permettent d'obtenir à la fois des couplages symétriques et des algorithmes efficaces pour leur calcul. Nous décrivons alors une approche unifiée permettant d'établir une large variété d'algorithmes calculant des couplages. Nous l'appliquons notamment à la construc- tion d'un nouvel algorithme pour le calcul de couplages sur des courbes supersin- gulières de genre 2 et de caractéristique 2. Les calculs nécessaires aux couplages que nous décrivons s'appuient sur l'implé- mentation d'une arithmétique rapide pour les corps finis de petite caractéristique : la multiplication est l'opération critique qu'il convient d'optimiser. Nous présen- tons donc un algorithme de recherche exhaustive de formules de multiplication. Enfin, nous appliquons toutes les méthodes précédentes à la conception et l'im- plémentation de différents accélérateurs matériels pour le calcul de couplages sur différentes courbes dont les architectures ont été optimisées soit pour leur rapidité, soit pour leur compacité.

La conception des bibliothèques d’évaluation de fonctions est un activité complexe qui requiert beaucoup de soin et d’application, particulièrement lorsque l’on vise des niveaux élevés de fiabilité et de performances. En pratique et de manière habituelle, on ne peut se livrer à ce travail sans disposer d’outils qui guident le concepteur dans le dédale d’un espace de solutions étendu et complexe mais qui lui garantissent également la correction et la quasi-optimalité de sa production. Dans l’état actuel de l’art, il nous faut encore plutôt raisonner en termes de « boite à outils » d’où le concepteur doit tirer et combiner des mécanismes de base, au mieux de ses objectifs, plutôt qu’imaginer que l’on dispose d’un dispositif à même de résoudre automatiquement tous les problèmes.Le présent travail s’attache à la conception et la réalisation de tels outils dans deux domaines:∙ la consolidation du test d’arrondi de Ziv utilisé, jusqu’à présent de manière plus ou moins empirique, dans l’implantation des approximations de fonction ;∙ le développement d’une implantation de l’algorithme SLZ dans le but de résoudre le « Dilemme du fabricant de table » dans le cas de fonctions ayant pour opérandes et pour résultat approché des nombres flottants en quadruple précision (format Binary64 selon la norme IEEE-754). / The design of function evaluation libraries is a complex task that requires a great care and dedication, especially when one wants to satisfy high standards of reliability and performance. In actual practice, it cannot be correctly performed, as a routine operation, without tools that not only help the designer to find his way in a complex and extended solution space but also to guarantee that his solutions are correct and (almost) optimal. As of the present state of the art, one has to think in terms of “toolbox” from which he can smartly mix-and-match the utensils that fit better his goals rather than expect to have at hand a solve-all automatic device.The work presented here is dedicated to the design and implementation of such tools in two realms:∙ the consolidation of Ziv’s rounding test that is used, in a more or less empirical way, for the implementation of functions approximation;∙ the development of an implementation of the SLZ-algorithm in order to solve the Table Maker Dilemma for the function with quad-precision floating point (IEEE-754 Binary128 format) arguments and images.

Une arithmétique sûre et efficace est un élément clé pour exécuter des calculs rapides et sûrs. Le choix du système numérique et des algorithmes arithmétiques est important. Nous présentons une nouvelle représentation des nombres, les "RN-codes", telle que tronquer un RN-code à une précision donnée est équivalent à l'arrondir au plus près. Nous donnons des algorithmes arithmétiques pour manipuler ces RN-codes et introduisons le concept de "RN-code en virgule flottante." Lors de l'implantation d'une fonction f en arithmétique flottante, si l'on veut toujours donner le nombre flottant le plus proche de f(x), il faut déterminer si f(x) est au-dessus ou en-dessous du plus proche "midpoint", un "midpoint" étant le milieu de deux nombres flottants consécutifs. Pour ce faire, le calcul est d'abord fait avec une certaine précision, et si cela ne suffit pas, le calcul est recommencé avec une précision de plus en plus grande. Ce processus ne s'arrête pas si f(x) est un midpoint. Étant donné une fonction algébrique f, soit nous montrons qu'il n'y a pas de nombres flottants x tel que f(x) est un midpoint, soit nous les caractérisons ou les énumérons. Depuis le PowerPC d'IBM, la division en binaire a été fréquemment implantée à l'aide de variantes de l'itération de Newton-Raphson dues à Peter Markstein. Cette itération est très rapide, mais il faut y apporter beaucoup de soin si l'on veut obtenir le nombre flottant le plus proche du quotient exact. Nous étudions comment fusionner efficacement les itérations de Markstein avec les itérations de Goldschmidt, plus rapides mais moins précises. Nous examinons également si ces itérations peuvent être utilisées pour l'arithmétique flottante décimale. Nous fournissons des bornes d'erreurs sûres et précises pour ces algorithmes. / Efficient and reliable computer arithmetic is a key requirement to perform fast and reliable numerical computations. The choice of the number system and the choice of the arithmetic algorithms are important. We present a new representation of numbers, the "RN-codings", such that truncating a RN-coded number to some position is equivalent to rounding it to the nearest. We give some arithmetic algorithms for manipulating RN-codings and introduce the concept of "floating-point RN-codings". When implementing a function f in floating-point arithmetic, if we wish to always return the floating-point number nearest f(x), one must be able to determine if f(x) is above or below the closest "midpoint", where a midpoint is the middle of two consecutive floating-point numbers. This determination is first done with some given precision, and if it does not suffice, we start again with higher precision, and so on. This process may not terminate if f(x) can be a midpoint. Given an algebraic function f, we try either to show that there are no floating-point numbers x such that f(x) is a midpoint, or we try to enumerate or characterize them. Since the IBM PowerPC, binary division has frequently been implemented using variants of the Newton-Raphson iteration due to Peter Markstein. This iteration is very fast, but much care is needed if we aim at always returning the floating-point number nearest the exact quotient. We investigate a way of efficiently merging Markstein iterations with faster yet less accurate iterations called Goldschmidt iterations. We also investigate whether those iterations can be used for decimal floating-point arithmetic. We provide sure and tight error bounds for these algorithms.

Dans la cryptographie à clé privée l'arithmétique joue un rôle important. En particulier, l'arithmétique des corps finis doit être très rapide étant donnée la quantité de calculs effectués en nécessitant des ressources limitées (surface de circuit, taille mémoire, consommation d'énergie) mais aussi tout en offrant un bon niveau de robustesse vis à vis des attaques physiques. L'objectif de cette thèse etait d'étudier, comparer, concevoir en matériel et enfin de valider expérimentalement et théoriquement des opérateurs arithmétiques matériels pour la cryptographie sur courbes elliptiques (ECC) sur des extensions du corps fini binaire (GF(2m)) à la fois performants, peu gourmands en énergie et robustes d'un point de sécurité contre les attaques physiques par canaux cachés (p.ex. mesure de la consommation d'énergie). Des travaux effectues aboutissent à la proposition d'opérateurs de multiplication performants (rapides, surface de circuit limitée) dans une architecture modulaire (pouvant être adaptée à des besoins spécifiques sans perte de performance). Les calculs requis par ces opérateurs sont complexes car les éléments du corps sont grands (160-580 bits) et la multiplication s'effectue modulo un polynôme irréductible. En plus la thèse presente des modification et l'optimisation des opérateurs pour les rendre plus robustes à certaines attaques par canaux cachés (de type mesure de consommation) sans perte de performance. Sécurisation d'opérateurs arithmétiques pour ECC au niveau des calculs sur le corps fini est particulièrement intéressant car c'est la première proposition de ce type. Ce travail complète un état de l'art en protections aux niveaux supérieurs (courbes, protocoles).

La cryptographie basée sur les courbes elliptiques (ECC) est de plus en plus utilisée dans les cryptosystèmes à clé publique, notamment parce qu'à niveau de sécurité équivalent, la taille nécessaire des clés ECC est nettement inférieure à ce que son prédécesseur, le RSA, requiert. L'ECC conduit donc à implanter des circuits plus compacts que pour le RSA, ce qui indique qu'elle est plus adaptée aux circuits fortement contraints (cartes à puce, etc.). L'ECC a d'ailleurs bénéficié de l'amélioration continue de l'arithmétique (des ordinateurs et des courbes) ces dernières années, ce qui lui permet de se positionner comme un remplaçant crédible au RSA dans le monde industriel. Il est vrai qu'un concepteur de circuits cryptographiques doit chercher à améliorer les performances de son cryptosystème, mais il doit également protéger ce dernier contre des attaques physiques pouvant compromettre sa sécurité. En effet, des attaques efficaces dites "par observation" et "par perturbation" ont été mises en évidence. Le concepteur de circuits cryptographiques doit donc implanter des parades à ces attaques, également appelées contre-mesures. Cependant, l'ajout de ces contre-mesures ne doit pas d'une part ajouter de nouvelles vulnérabilités au cryptosystème, et d'autre part diminuer drastiquement ses performances. Ces travaux de thése proposent une nouvelle architecture d'unité arithmétique pour l'ECC. Il se trouve que les performances de cette derniére sont meilleures que la plupart de celles présentes dans la littérature. Ceci est essentiellement dû à l'utilisation d'une représentation redondante des nombres, appelée repréesentation à retenues signées. Le second r'ésultat principal de ces travaux provient de la protection de cette unité contre les attaques par observation à l'aide de l'état de l'art : ce faisant, nous proposons là encore la solution la plus performante de la littérature. Enfin, nous avons exploré la possibilié de protéger notre circuit contre les attaques par perturbation à l'aide du principe de la préservation de la parité. Cette dernière contribution amène des réesultats encourageants

Ce travail présente quelques contributions en arithmétique des ordinateurs pour le matériel et le logiciel. L'arithmétique des ordinateurs est la branche de l'informatique qui traite des représentations des nombres, des algorithmes pour effectuer les calculs de base en machine, la validation de la qualité des calculs, l'analyse de l'efficacité des calculs et des outils d'aide à la conception de systèmes de calcul arithmétique. Nos travaux comportent des liens avec les domaines de la conception de circuits intégrés numériques, de l'architecture des machines et du développement logiciel de bibliothèques de calcul. Les principaux domaines d'application de nos travaux sont: le calcul numérique dans les systèmes embarqués, la cryptographie et la sécurité numérique, le traitement numérique du signal et des images et de façon plus limitée les dispositifs numériques de contrôle-commande en automatique. Le mémoire résume les travaux de recherche effectués, seul et en collaboration, depuis octobre 1997. Ces travaux portent sur: l'arithmétique en ligne, des architectures reconfigurables, des méthodes d'évaluation de fonctions à base de tables, la division pour circuits asynchrones, des opérateurs arithmétiques spécifiques pour FPGA, des variantes de la multiplication comme la multiplication par des constantes ou tronquée, des bibliothèques flottantes pour processeurs entiers, la division par des constantes, l'évaluation de fonctions par approximation polynomiale, des opérateurs arithmétiques pour la basse consommation d'énergie, la modélisation et l'évaluation de la consommation d'opérateurs arithmétiques, des opérateurs arithmétiques pour la cryptographie (corps finis et sécurisation contre des attaques physiques), la génération de diviseurs matériels, la bibliothèque logicielle PACE pour la cryptographie, la consommation d'énergie dans les processeurs graphiques, la maîtrise des erreurs d'arrondi dans les outils de CAO, la génération de nombres vraiment aléatoires et l'arithmétique par estimation.

Le calcul rigoureux vise à produire des représentations certifiées pour les solutions de nombreux problèmes, notamment en analyse fonctionnelle, comme des équations différentielles ou des problèmes de contrôle optimal. En effet, certains domaines particuliers comme l’ingénierie des systèmes critiques ou les preuves mathématiques assistées par ordinateur ont des exigences de fiabilité supérieures à ce qui peut résulter de l’utilisation d’algorithmes relevant de l’analyse numérique classique.Notre objectif consiste à développer des algorithmes à la fois efficaces et validés / certifiés, dans le sens où toutes les erreurs numériques (d’arrondi ou de méthode) sont prises en compte. En particulier, nous recourons aux approximations polynomiales rigoureuses combinées avec des méthodes de validation a posteriori à base de points fixes. Ces techniques sont implémentées au sein d’une bibliothèque écrite en C, ainsi que dans un développement de preuve formelle en Coq, offrant ainsi le plus haut niveau de confiance, c’est-à-dire une implémentation certifiée.Après avoir présenté les opérations élémentaires sur les approximations polynomiales rigoureuses, nous détaillons un nouvel algorithme de validation pour des approximations sous forme de séries de Tchebychev tronquées de fonctions D-finies, qui sont les solutions d’équations différentielles ordinaires linéaires à coefficients polynomiaux. Nous fournissons une analyse fine de sa complexité, ainsi qu’une extension aux équations différentielles ordinaires linéaires générales et aux systèmes couplés de telles équations. Ces méthodes dites symboliques-numériques sont ensuite utilisées dans plusieurs problèmes reliés : une nouvelle borne sur le nombre de Hilbert pour les systèmes quartiques, la validation de trajectoires de satellites lors du problème du rendez-vous linéarisé, le calcul de polynômes d’approximation optimisés pour l’erreur d’évaluation, et enfin la reconstruction du support et de la densité pour certaines mesures, grâce à des techniques algébriques. / Rigorous numerics aims at providing certified representations for solutions of various problems, notably in functional analysis, e.g., differential equations or optimal control. Indeed, specific domains like safety-critical engineering or computer-assisted proofs in mathematics have stronger reliability requirements than what can be achieved by resorting to standard numerical analysis algorithms. Our goal consists in developing efficient algorithms, which are also validated / certified in the sense that all numerical errors (method or rounding) are taken into account. Specifically, a central contribution is to combine polynomial approximations with a posteriori fixed-point validation techniques. A C code library for rigorous polynomial approximations (RPAs) is provided, together with a Coq formal proof development, offering the highest confidence at the implementation level.After providing basic operations on RPAs, we focus on a new validation algorithm for Chebyshev basis solutions of D-finite functions, i.e., solutions of linear ordinary differential equations (LODEs) with polynomial coefficients. We give an in-depth complexity analysis, as well as an extension to general LODEs, and even coupled systems of them. These symbolic-numeric methods are finally used in several related problems: a new lower bound on the Hilbert number for quartic systems; a validation of trajectories arising in the linearized spacecraft rendezvous problem; the design of evaluation error efficient polynomial approximations; and the support and density reconstruction of particular measures using algebraic techniques.

Les protocoles de cryptographie asymétrique nécessitent des calculs arithmétiques dans différentes structures mathématiques. Un grand nombre de ces protocoles requièrent en particulier des calculs dans des structures finies, rendant indispensable une arithmétique modulaire efficace. Ces opérations modulaires sont composées d'opérations multiprécision entre opérandes de tailles suffisamment grandes pour garantir le niveau de sécurité requis (de plusieurs centaines à plusieurs milliers de bits). Enfin, certains protocoles nécessitent des opérations arithmétiques dans le groupe des points d'une courbe elliptique, opérations elles-mêmes composées d'opérations dans le corps de définition de la courbe. Les tailles de clés utilisées par les protocoles rendent ainsi les opérations arithmétiques coûteuses en temps de calcul. Par ailleurs, les architectures grand public actuelles embarquent plusieurs unités de calcul, réparties sur les processeurs et éventuellement sur les cartes graphiques. Ces ressources sont aujourd'hui facilement exploitables grâce à des interfaces de programmation parallèle comme OpenMP ou CUDA. Cette thèse s'articule autour de la définition d'opérateurs arithmétiques parallèles permettant de tirer parti de l'ensemble des ressources de calcul, en particulier sur des architectures multicœur à mémoire partagée. La parallélisation au niveau arithmétique le plus bas permet des gains modérés en termes temps de calcul, car les tailles des opérandes ne sont pas suffisamment importantes pour que l'intensité arithmétique des calculs masque les latences dues au parallélisme. Nous proposons donc des algorithmes permettant une parallélisation aux niveaux arithmétiques supérieurs : algorithmes parallèles pour la multiplication modulaire et pour la multiplication scalaire sur les courbes elliptiques. Pour la multiplication modulaire, nous étudions en particulier plusieurs ordonnancements des calculs au niveau de l'arithmétique modulaire et proposons également une parallélisation à deux niveaux : modulaire et multiprécision. Ce parallélisme à plus gros grain permet en pratique des gains plus conséquents en temps de calcul. Nous proposons également une parallélisation sur processeur graphique d'opérations modulaires et d'opérations dans le groupe des points d'une courbe elliptique. Enfin, nous présentons une méthode pour optimiser la multiplication scalaire sur les courbes elliptiques pour de petits scalaires.

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.