Reynald Lercier

R. Lercier. Algorithmique des Courbes Elliptiques dans les Corps Finis. Thèse de Doctorat, École polytechnique, Palaiseau, Juin 1997.

Cette thèse est consacrée au calcul du nombre de points d'une courbe elliptique définie sur un corps fini. Nous étudions dans une première partie l'algorithme de Schoof et ses variantes dues à Atkin et à Elkies. Nous montrons ainsi en quelle mesure ces algorithmes, initialement prévus pour des corps de grande caractéristique, peuvent s'appliquer à ceux de petite caractéristique.

Il s'avère que la majeure partie des idées d'Atkin et Elkies sont applicables à cette dernière famille de corps, à quelques modifications mineures près, excepté le calcul d'isogénies entre courbes elliptiques. C'est pourquoi, nous étudions dans une deuxième partie cinq algorithmes de calcul d'isogénies. Le premier algorithme est l'algorithme original d'Atkin pour le cas des corps de grande caractéristique. Les deuxième et troisième algorithme sont ceux de Couveignes pour les corps de petite caractéristique. Enfin, nous proposons à notre tour un quatrième algorithme pour le cas spécifique de la caractéristique deux et montrons dans un cinquième algorithme comment ces idées peuvent se généraliser à des corps de caractéristique p impaire pour des isogénies de degré l borné par 2p.

D'un point de vue plus pratique, nous explicitons dans une troisième partie les méthodes de programmation mises en oeuvre pour implanter les algorithmes précédents. Nous y présentons notamment ZEN, une librairie de calcul qui permet une programmation efficace en langage C de toute extension algébrique d'un anneau fini. Enfin, nous expliquons comment nous utilisons le programme obtenu pour calculer efficacement le nombre de points de courbes définies dans tout corps finis à moins de 10¹⁰⁰ éléments. En particulier, nous montrons comment trouver ainsi des courbes elliptiques ayant de bonnes propriétés cryptographiques.

[ bib | preprint | publication ] Retour