Le codage et le comportement de l'arithmétique à virgule flottante disponible dans les ordinateurs sont spécifiés par la norme IEEE-754. Cette norme impose au système de rendre comme résultat de l'une des quatre opérations (+, *, /, sqrt), l'arrondi du résultat exact. Cette propriété que l'on appelle <>, permet de garantir la qualité du résultat. Elle permet également la construction de preuves d'algorithmes, quelles que soient les machines sur lesquelles l'opération est executée. Toutefois cette norme présente des limites, puisque les fonctions élémentaires (sinus, cosinus, exponentielle...) en sont absentes. Cette abscence est liée au <> : il est, contrairement aux opérations de base, difficile de connaître la précision nécessaire pour garantir l'arrondi correct des fonctions élémentaires. Cependant, si l'on fixe le format de représentation, il est alors possible par une recherche exhaustive de déterminer cette borne; ce fut le travail de thèse de Lefèvre pour la double précision. <br /><br />L'objectif de ce mémoire est d'exploiter les bornes associées à chaque fonction, pour certifier l'arrondi correct des fonctions élémentaires en double précision pour les quatre modes d'arrondi. À cet effet, nous avons implémenté les évaluations en deux étapes : l'une rapide et juste la plupart du temps, basée sur les propriétés de l'arithmétique IEEE double précision, et l'autre juste tout le temps, composé d'opérateurs multiprécision. Pour cette deuxième phase, nous avons développé une bibliothèque d'opérateurs multiprécision optimisés pour les précisions données par ces bornes et les caractéristiques des processeurs en 2003.

Les protocoles de cryptographie asymétrique nécessitent des calculs arithmétiques dans différentes structures mathématiques de grandes tailles. Pour garantir une sécurité suffisante, ces tailles varient de plusieurs centaines à plusieurs milliers de bits et rendent les opérations arithmétiques coûteuses en temps de calcul. D'autre part, 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. Dans cette thèse, nous étudions la parallélisation d'opérateurs à différents niveaux arithmétique. Nous nous intéressons plus particulièrement à la multiplication entre entiers multiprécision ; à la multiplication modulaire ; et enfin à la multiplication scalaire sur les courbes elliptiques.Dans chacun des cas, nous étudions différents ordonnancements des calculs permettant d'obtenir les meilleures performances. Nous proposons également une bibliothèque permettant la parallélisation sur processeur graphique d'instances d'opérations modulaires et d'opérations sur les courbes elliptiques. Enfin, nous proposons une méthode d'optimisation automatique de la multiplication scalaire sur les courbes elliptiques pour de petits scalaires permettant l'élimination des sous-expressions communes apparaissant dans la formule et l'application systématique de transformations arithmétiques. / Asymmetric cryptography requires some computations in large size finite mathematical structures. To insure the required security, these sizes range from several hundred to several thousand of bits. Mathematical operations are thus expansive in terms of computation time. Otherwise, current architectures have several computing units, which are distribued over the processors and GPU and easily implementable using dedicated languages as OpenMP or CUDA. In this dissertation, we investigate the parallelization of some operators for different arithmetical levels.In particular, our research focuse on parallel multiprecision and modular multiplications, and the parallelization of scalar multiplication over elliptic curves. We also propose a library to parallelize modular operations and elliptic curves operations. Finally, we present a method which allow to optimize scalar elliptic curve multiplication for small scalars.

L'application d'Abel-Jacobi fait le lien entre la forme de Weierstrass d'une courbe elliptique définie sur C et le tore complexe qui lui est associé. Il est possible de la calculer en un nombre d'opérations quasi-linéaire en la précision voulue, c'est à dire en temps O(M(P) log P). Son inverse est donné par la fonction p de Weierstrass, qui s'exprime en fonction de thêta, une fonction importante en théorie des nombres. L'algorithme naturel d'évaluation de thêta nécessite O(M(P) sqrt(P)) opérations, mais certaines valeurs (les thêta-constantes) peuvent être calculées en O(M(P) log P) opérations en exploitant les liens avec la moyenne arithmético-géométrique (AGM). Dans ce manuscrit, nous généralisons cet algorithme afin de calculer thêta en O(M(P) log P). Nous exhibons une fonction F qui a des propriétés similaires à l'AGM. D'une façon similaire à l'algorithme pour les thêta-constantes, nous pouvons alors utiliser la méthode de Newton pour calculer la valeur de thêta. Nous avons implanté cet algorithme, qui est plus rapide que la méthode naïve pour des précisions supérieures à 300 000 chiffres décimaux. Nous montrons comment généraliser cet algorithme en genre supérieur, et en particulier comment généraliser la fonction F. En genre 2, nous sommes parvenus à prouver que la même méthode mène à un algorithme qui évalue thêta en O(M(P) log P) opérations ; la même complexité s'applique aussi à l'application d'Abel-Jacobi. Cet algorithme est plus rapide que la méthode naïve pour des précisions plus faibles qu'en genre 1, de l'ordre de 3 000 chiffres décimaux. Nous esquissons également des pistes pour obtenir la même complexité en genre quelconque. Enfin, nous exhibons un nouvel algorithme permettant de calculer une isogénie de courbes elliptiques de noyau donné. Cet algorithme utilise l'application d'Abel-Jacobi, car il est facile d'évaluer l'isogénie sur le tore ; il est sans doute possible de le généraliser au genre supérieur / The Abel-Jacobi map links the short Weierstrass form of a complex elliptic curve to the complex torus associated to it. One can compute it with a number of operations which is quasi-linear in the target precision, i.e. in time O(M(P) log P). Its inverse is given by Weierstrass's p-function, which can be written as a function of theta, an important function in number theory. The natural algorithm for evaluating theta requires O(M(P) sqrt(P)) operations, but some values (the theta-constants) can be computed in O(M(P) log P) operations by exploiting the links with the arithmetico-geometric mean (AGM). In this manuscript, we generalize this algorithm in order to compute theta in O(M(P) log P). We give a function F which has similar properties to the AGM. As with the algorithm for theta-constants, we can then use Newton's method to compute the value of theta. We implemented this algorithm, which is faster than the naive method for precisions larger than 300,000 decimal digits. We then study the generalization of this algorithm in higher genus, and in particular how to generalize the F function. In genus 2, we managed to prove that the same method leads to a O(M(P) log P) algorithm for theta; the same complexity applies to the Abel-Jacobi map. This algorithm is faster than the naive method for precisions smaller than in genus 1, of about 3,000 decimal digits. We also outline a way one could reach the same complexity in any genus. Finally, we study a new algorithm which computes an isogeny of elliptic curves with given kernel. This algorithm uses the Abel-Jacobi map because it is easy to evaluate the isogeny on the complex torus; this algorithm may be generalizable to higher genera

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.