Ce mémoire présente mes travaux de recherche de 1988 à 2001, travaux effectués d'abord à l'INRIA Rocquencourt au sein du projet Algo (1988 à 1992), puis à l'INRIA Lorraine et au LORIA dans les projets Euréca (1993 à 1997), PolKA (1998 à 2000), et Spaces (2001). Au niveau thématique, on peut distinguer grosso modo trois phases : une première période allant de 1988 à 1992 où j'ai surtout travaillé sur l'analyse d'algorithmes et la génération aléatoire, une seconde période de 1993 à 1997 où je me suis investi dans le calcul formel et les algorithmes sous-jacents, enfin une troisième période depuis 1998 où je me suis intéressé aux problèmes d'arithmétique exacte en précision arbitraire.

Dans ce mémoire, nous présentons divers travaux sur le thème de l'algorithmique des courbes algébriques en vue d'applications à la cryptologie. Nous décrivons des algorithmes pour le calcul de logarithmes discrets, problème dont la difficulté est à la base de la sécurité des cryptosystèmes s'appuyant sur les courbes. Une première classe d'algorithmes regroupe les techniques du type «calcul d'index»; une seconde les méthodes liées à la restriction de Weil. Viennent ensuite des algorithmes permettant le calcul du nombre de points d'une courbe définie sur un corps fini. Ceux-ci se répartissent en trois catégories: l'algorithme de Schoof et ses généralisations, les algorithmes p-adiques s'appuyant sur un relèvement canonique, et les méthodes p-adiques issues de l'algorithme de Kedlaya. Nous traitons d'autres aspects pouvant être utiles lors de la conception de cryptosystèmes à bases de courbes, en particulier des formules efficaces pour la loi de groupe en genre 2, issues de la théorie des fonctions Thêta. Pour finir, nous mentionnons des travaux liés à l'arithmétique efficace et son implantation logicielle, notamment des travaux sur l'algorithme de Schönhage-Strassen et sur une bibliothèque pour les corps finis.

Dans le domaine des sondages, il y a plusieurs méthodes d'estimer une moyenne ou un total d'une population. Une des techniques les plus pratiques est l'utilisation d'une variable auxiliaire ayant une corrélation avec la variable d'intérêt et dont les données sur toute la population sont connues. Dans ce mémoire, on va s'intéresser particulièrement à l'estimation d'une moyenne par le quotient. Dans ce cadre, on va traiter largement cette approche, en détaillant premièrement tout ce qui concerne l'estimateur par le quotient afin de répondre à toute question sur le sujet. Par la suite, on va étudier un cas particulier de l'estimation par le quotient lorsque la variable étudiée est dichotomique, en examinant les estimateurs possibles selon le mode de tirage, soit le tirage avec probabilités égales ou probabilités inégales avec ou sans remise. Dans le dernier chapitre, on présentera le cas où la variable auxiliaire est aussi dichotomique. Quatre estimateurs seront proposés pour estimer la moyenne de la population. On va analyser leurs propriétés dans le but de pouvoir les comparer. Afin que le traitement théorique soit valable, on va le concrétiser par des simulations avec des populations réelles et d'autres générées selon des paramètres donnés. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Estimateur, Quotient, Variable auxiliaire, Variable dichotomique.

Un tour d'horizon de plusieurs systèmes de numération "exotiques" et leurs applications en cryptographie est proposé.

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 théorème de Gauss sur les sommes de 3 carrés relie le nombre de points entiers primitifs sur la sphère de rayon la racine carrée de n au nombre de classes d'un ordre quadratique imaginaire. En 2011, Edixhoven a esquissée une preuve du théorème de Gauss en utilisant une approche de la géométrie arithmétique. Il a utilisé l'action du groupe orthogonal spécial sur la sphère et a donné une bijection entre l'ensemble des SO3(Z)-orbites de tels points, si non vide, avec l'ensemble des classes d'isomorphisme de torseurs sous le stabilisateur. Ce dernier ensemble est un groupe, isomorphe au groupe des classes d'isomorphisme de modules projectifs de rang 1 sur l'anneau Z[1/2, √- n], ce qui donne une structure d'espace affine sur l'ensemble des SO3(Z)-orbites sur la sphère. Au chapitre 3 de cette thèse, nous donnons une démonstration complète du théorème de Gauss suivant les travaux d'Edixhoven. Nous donnons aussi une nouvelle preuve du théorème de Legendre sur l'existence d'une solution entière primitive de l'équation x2 + y2 + z2 = n en utilisant la théorie des faisceaux. Nous montrons au chapitre 4 comment obtenir explicitement l'action, donnée par la méthode des faisceaux, du groupe des classes sur l'ensemble des SO3(Z)-orbites sur la sphère en termes de SO3(Q). / Gauss's theorem on sums of 3 squares relates the number of primitive integer points on the sphere of radius the square root of n with the class number of some quadratic imaginary order. In 2011, Edixhoven sketched a different proof of Gauss's theorem by using an approach from arithmetic geometry. He used the action of the special orthogonal group on the sphere and gave a bijection between the set of SO3(Z)-orbits of such points, if non-empty, with the set of isomorphism classes of torsors under the stabilizer group. This last set is a group, isomorphic to the group of isomorphism classes of projective rank one modules over the ring Z[1/2, √- n]. This gives an affine space structure on the set of SO3(Z)-orbits on the sphere. In Chapter 3 we give a complete proof of Gauss's theorem following Edixhoven's work and a new proof of Legendre's theorem on the existence of a primitive integer solution of the equation x2 + y2 + z2 = n by sheaf theory. In Chapter 4 we make the action given by the sheaf method of the Picard group on the set of SO3(Z)-orbits on the sphere explicit, in terms of SO3(Q). / De stelling van Gauss over sommen van 3 kwadraten relateert het aantal primitieve gehele punten op de bol van straal de vierkantswortel van n aan het klassengetal van een bepaalde imaginaire kwadratisch orde. In 2011 schetste Edixhoven een ander bewijs van deze stelling van Gauss metbehulp van aritmetische meetkunde. Hij gebruikte de actie van de special orthogonale groep op de bol en gaf een bijectie tussen de verzameling van SO3(Z)-banen van dergelijke punten, als die niet leeg is, met de verzameling van isomor_e klassen van torsors onder de stabilisator groep. Deze laatste verzameling is een groep, isomorf met de groep van isomor_e klassen van projectieve rang _e_en modulen over de ring Z[1/2, √- n]. Dit geeft een a_ene ruimte structuur op de verzameling van SO3(Z)-banen op de bol. In Hoofdstuk 3 geven we een volledig bewijs van de stelling van Gauss zoals geschetst door Edixhoven, en een nieuw bewijs van Legendre's stelling over het bestaan van een primitieve gehele oplossing van de vergelijking x2 +y2 +z2 = n met schoven theorie. In hoofdstuk 4 maken we de werking gegeven door de schoven theorie van de Picard groep op de verzameling van SO3(Z)-banen op de bol expliciet, in termen van SO3(Q).

Cette thèse fait une étude sur deux moyens d'enrichir l'environnement flottant courant : le premier est d'obtenir plusieurs versions d'implantation pour chaque fonction mathématique, le deuxième est de fournir des opérations de la norme IEEE754, qui permettent de mélanger les entrées et la sortie dans les bases différentes. Comme la quantité de versions différentes pour chaque fonction mathématique est énorme, ce travail se concentre sur la génération du code. Notre générateur de code adresse une large variété de fonctions: il produit les implantations paramétrées pour les fonctions définies par l'utilisateur. Il peut être vu comme un générateur de fonctions boîtes-noires. Ce travail inclut un nouvel algorithme pour le découpage de domaine et une tentative de remplacer les branchements pendant la reconstruction par un polynôme. Le nouveau découpage de domaines produit moins de sous-domaines et les degrés polynomiaux sur les sous-domaines adjacents ne varient pas beaucoup. Pour fournir les implantations vectorisables il faut éviter les branchements if-else pendant la reconstruction. Depuis la révision de la norme IEEE754 en 2008, il est devenu possible de mélanger des nombres de différentes précisions dans une opération. Par contre, il n'y a aucun mécanisme qui permettrait de mélanger les nombres dans des bases différentes dans une opération. La recherche dans l'arithmétique en base mixte a commencé par les pires cas pour le FMA. Un nouvel algorithme pour convertir une suite de caractères décimaux du longueur arbitraire en nombre flottant binaire est présenté. Il est indépendant du mode d'arrondi actuel et produit un résultat correctement arrondi. / This work investigates two ways of enlarging the current floating-point environment. The first is to support several implementation versions of each mathematical function (elementary such as $\exp$ or $\log$ and special such as $\erf$ or $\Gamma$), the second one is to provide IEEE754 operations that mix the inputs and the output of different \radixes. As the number of various implementations for each mathematical function is large, this work is focused on code generation. Our code generator supports the huge variety of functions: it generates parametrized implementations for the user-specified functions. So it may be considered as a black-box function generator. This work contains a novel algorithm for domain splitting and an approach to replace branching on reconstruction by a polynomial. This new domain splitting algorithm produces less subdomains and the polynomial degrees on adjacent subdomains do not change much. To produce vectorizable implementations, if-else statements on the reconstruction step have to be avoided. Since the revision of the IEEE754 Standard in 2008 it is possible to mix numbers of different precisions in one operation. However, there is no mechanism that allows users to mix numbers of different radices in one operation. This research starts an examination ofmixed-radix arithmetic with the worst cases search for FMA. A novel algorithm to convert a decimal character sequence of arbitrary length to a binary floating-point number is presented. It is independent of currently-set rounding mode and produces correctly-rounded results.

Aujourd'hui encore, certains systèmes embarqués n'intègrent pas leur propre unité flottante, pour des contraintes de surface, de coût et de consommation d'énergie. Cependant, ce type d'architecture est largement utilisé dans des domaines d'application extrêmement exigeants en calculs flottants (le multimédia, l'audio et la vidéo ou les télécommunications). Pour compenser le fait que l'arithmétique flottante ne soit pas implantée en matériel, elle doit être émulée efficacement à travers une implantation logicielle. Cette thèse traite de la conception et de l'implantation d'un support logiciel efficace pour l'arithmétique virgule flottante IEEE 754 aux processeurs entiers embarqués. Plus spécialement, elle propose de nouveaux algorithmes et outils pour la génération efficace de programmes à la fois rapides et certifiés, permettant notamment d'obtenir des codes C de très faibles latences pour l'évaluation polynomiale en arithmétique virgule fixe. Comparés aux implantations complètement écrites à la main, ces outils permettent de réduire de manière significative le temps de développement d'opérateurs flottants. La première partie de la thèse traite de la conception d'algorithmes optimisés pour certains opérateurs flottants en base 2, et donne des détails sur leur implantation logicielle pour le format virgule flottante binary32 et pour certains processeurs VLIW entiers embarqués comme ceux de la famille ST200 de STMicroelectronics. En particulier, nous proposons ici une approche uniforme pour l'implantation correctement arrondie des racines et de leur inverse, ainsi qu'une extension à la division. Notre approche, qui repose sur l'évaluation d'un seul polynôme bivarié, permet d'exprimer un plus haut degré de parallélisme d'instruction (ILP) que les méthodes précédentes, et s'avère particulièrement efficace en pratique. Ces travaux nous ont permis de fournir une version complètement remaniée de la bibliothèque FLIP, entraînant des gains significatifs par rapport à la version précédente. La deuxième partie de la thèse présente une méthodologie pour générer automatiquement et efficacement des codes C rapides et certifiés pour l'évaluation de polynômes bivariés en arithmétique virgule fixe. En particulier, elle consiste en un ensemble d'heuristiques pour calculer des schémas d'évaluation très parallèles et de faible latence, ainsi qu'un ensemble de techniques pour vérifier si ces schémas restent efficaces sur une architecture cible réelle et suffisamment précis pour garantir l'arrondi correct de l'implantation des opérateurs sous-jacente. Cette approche a été implantée dans l'environnement logiciel CGPE (Code Generation for Polynomial Evaluation). Nous avons ainsi utilisé notre outil pour générer et certifier rapidement des parties significatives des codes de la bibliothèque FLIP.

Les progrès enregistrés en modélisation solide ont beaucoup contribué à l'essor des diverses applications de la CAO/FAO, de la robotique et de la synthèse d'images. Les systèmes de modélisation solide contemporains combinent souvent la représentation par arbre de construction et la représentation par frontière afin de mieux répondre aux besoins des applications. Dans cette thèse nous proposons une nouvelle méthode de calcul de la frontière d'un objet polyédrique décrit par un arbre de construction, qui traite uniformément les nombreux cas particuliers et qui résout le problème crucial des imprécisions numériques inhérentes à l'arithmétique flottante. Une implantation utilisant une arithmétique rationnelle optimisée est présentée ainsi que des résultats de tests.

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é.