Algorithmique des courbes elliptiques dans les corps finis

Algorithme de Schoof

 Avec la publication en 1985 d’un algorithme déterministe de complexité en O(log8q) pour calculer le nombre de points d’une courbe elliptique définie sur un corps fini Fq [101], Schoof offrait une alternative fort alléchante aux méthodes de complexité en O(q 1/4log2q) connues jusqu’alors. En effet, avec par exemple l’algorithme “des pas de bébé et de géant” de Shanks [107], il n’est pas envisageable d’avoir q > 1030. Néanmoins, l’algorithme de Schoof n’aurait pas pris l’importance que nous lui connaissons aujourd’hui sans d’une part, les travaux d’Atkin qui, au travers de deux communications importantes [4, 5], montre comment calculer le nombre de points d’une courbe définie sur F10275+693, et d’autre part, les travaux d’Elkies [39] qui complètent ceux d’Atkin. À l’invitation d’Atkin qui écrit en 1992, “since there is now considerable variety in the mathematics and programming involved in the problem, it  is to be hoped that more people will try their hand at it”, de nombreuses améliorations ont suivi, notamment l’obtention de la cardinalité d’une courbe elliptique modulo des puissances de nombres premiers [34, 33]. Tous ces travaux forment le corps d’un algorithme probabiliste appelé l’algorithme SEA dont la complexité est de O(log6q). Notre but est ici de donner un panorama relativement complet de ces idées en nous plaçant délibérément dans un corps fini Fq quelconque. Nous serons ainsi mieux à même d’appréhender l’utilité des algorithmes de la partie II. Une fois rappelé comment s’applique la méthode de Shanks aux courbes elliptiques (section 3.1), nous faisons un rappel de l’algorithme original de Schoof (section 3.2) avant d’expliquer en quoi les méthodes efficaces de calcul d’équations modulaires développées par Atkin améliorent sensiblement cet algorithme (section 3.3). Enfin, nous expliquons comment, à partir de ces équations modulaires, la détermination d’isogénies préconisée par Elkies permet aux implantations les plus optimisées pour Z/pZ comme celle de Morain [91] d’atteindre des corps aussi gros que F10499+153 (section 3.4).

Cycle d’isogénies

   Pour déterminer la trace c du Frobenius φE modulo une puissance de nombre premier ℓk, nous utilisons la même idée que pour déterminer c mod ℓ, c’est-à-dire projeter l’équation caractéristique du Frobenius sur E, l’un des ℓk sous-groupes d’ordre ℓk de E[ℓk]. La difficulté étant le calcul explicite de E, il est naturel, suite aux idées précédentes, de le rechercher comme le noyau d’une isogénie I de degré ℓk. Couveignes, Dewaghe et Morain [34, 33] proposent deux variantes d’une même idée pour calculer I. Ainsi, s’ils réitèrent k fois le calcul d’une isogénie de degré ℓ dont la composition mène à une isogénie de degré ℓk, c’est l’ensemble de définition de I qu’ils font varier. Dans une première variante, I a pour ensemble de définition E et est obtenue par récurrence comme la composition d’une isogénie de degré ℓ dont l’ensemble de définition est la courbe d’arrivée d’une isogénie de degré ℓk−1. L’inconvénient de cette méthode est qu’il n’est possible de tirer parti de la présence d’un facteur de petit degré du dénominateur I qu’en factorisant le numérateur de toutes les isogénies de degré ℓ. La deuxième variante permet de remplacer ces k factorisations par la seule factorisation d’une isogénie de degré ℓ définie à partir de E en composant une isogénie de degré ℓ dont l’ensemble d’arrivée est cette fois l’image d’une isogénie de degré ℓk−1 .

Isogénies et points de 2-torsion

   Manifestement, les relations sous-jacentes à l’algorithme du chapitre 7 pour F2n découlent de la translation TPa par le point Pa d’ordre 2 de la courbe. Pour généraliser cet algorithme à d’autres corps finis, il est donc naturel de se préoccuper aussi de cette translation et nous montrons dans une première partie comment obtenir, à partir de celle-ci, une caractérisation des isogénies semblable à celle du chapitre 7. Nos tentatives pour tirer un algorithme complet de ces résultats se sont malheureusement soldé pas un échec. Néanmoins, nous expliquons dans une deuxième partie comment une application immédiate nous permet de déduire d’une part les coefficients du numérateur g(X) de l’abscisse g(X)/h2 (X) d’une isogénie linéairement en fonction de ceux de h2(X), et d’autre part au moins (ℓ − 1)/2 relations linéaires entre les coefficients de h2(X).

pgcd simples

   Les pgcd simples considérés sont les suivants.
– Euclide : la routine Euclide de l’algorithme 9.1 qui va nous servir de référence.
– Lehmer : la routine Lehmer de l’algorithme 9.2 associée à la fonction partielle Euclidien_partiel de l’algorithme 9.5.
– binaire : la routine schéma_binaire de l’algorithme 9.8 associée à la fonction partielle binaire_partiel de l’algorithme 9.9.
– plus_minus : la routine schéma_binaire de l’algorithme 9.6 associée à la fonction partielle plus_minus_partiel de l’algorithme 9.9.
– binaire_généralisé : la routine binaire_généralisé de l’algorithme 9.13 avec un appel à la routine conjugue de l’algorithme 9.11 réalisée en double précision. Il apparaît au travers de ces courbes que le meilleur algorithme dépend fortement de l’architecture utilisée. La raison essentielle est l’absence dans l’assembleur des processeurs alpha des machines DEC d’une instruction de division (présente par contre sur les processeurs sparc des SUN), ce qui pénalise Euclide. Les algorithmes binaire et plus_minus semblent néanmoins être une bonne alternative. Ainsi,par exemple, calculer un pgcd de deux entiers de 100 mots de 64 bits est sur une station DEC environ 10 fois plus rapide par celui-ci que par l’algorithme Euclide, mais seulement 5 fois plus rapide pour 100 mots de 32 bits sur une station SUN. L’efficacité de ces méthodes est modulée par la taille des entiers. Ainsi, les algorithmes dont les fonctions partielles sont rapides à calculer (comme, par exemple, binaire_partiel) sont avantagés pour les petites longueurs car il s’agit alors du coût majeur de ces derniers.

Algorithmique

   Du point de vue algorithmique, ZEN tire parti de la collaboration de l’auteur à deux librairies qui n’ont pas été diffusées. D’une part, la librairie CESAR initiée par Morain pour Z/pZ et d’autre part, la librairie GFM, initiée par Chabaud pour F2n . Les algorithmes qui y sont programmés ayant été longuement optimisés (voir à ce sujet [88, 65, 21]), ils ont bien sûr été une source d’inspiration précieuse pour ZEN. Néanmoins, ZEN est autre chose que la réunion de CESAR et de GFM. Le facteur déterminant pour une implantation optimale est le choix de la structure informatique sous-jacente au stockage des éléments, polynômes, etc, du corps fini considéré. Pour les entiers de taille arbitraire, il est ainsi maintenant communément admis que la structure informatique optimale pour les stocker est un tableau contigu de “mots” (entiers de la taille Ω des registres de la machine, généralement 32 ou 64 bits). C’est ce qui est programmé dans BigNum et certaines des routines de CESAR qui ont pour arguments ces entiers ont été reprises en y ajoutant la gestion des erreurs décrite au paragraphe précédent. Cela est par exemple le cas du pgcd d’entiers développé initialement par l’auteur pour CESAR et décrit dans le chapitre 9, de la racine carré ou du logarithme approché d’un entier développés par F. Morain. . . Pour les corps finis, la situation est moins aisée puisque les structures optimales dépendent du corps fini et plus précisément de sa caractéristique et de sa taille. Nous décrivons dans la suite celles de ZEN,description certes un peu rébarbative, mais indispensable pour se rendre compte du travail réalisé. Nous donnons pour chaque type de corps, la structure informatique correspondante pour les éléments, les polynômes et les matrices. Pour les séries tronquées et les courbes elliptiques, également implantés dans ZEN, le besoin d’une structure adaptée ne s’est pas encore fait sentir et celle-ci est identique pour tous les corps.

Table des matières

Introduction
I Algorithme SEA 
1 Corps finis 
1.1 Définition
1.2 Cardinalité
1.3 Groupe multiplicatif
1.4 Sous-corps d’un corps fini
1.5 Automorphismes d’un corps fini
1.6 Existence
2 Courbes elliptiques définies sur des corps finis 
2.1 Généralités
2.1.1 Définition
2.1.2 Loi de groupe
2.1.3 Morphismes
2.1.4 Spécialisation à C
2.1.5 Spécialisation aux corps finis
2.2 Courbes particulières
2.2.1 Cas jE = 0
2.2.2 Cas jE = 1728
2.2.3 Autres invariants supersinguliers
3 Algorithme de Schoof 
3.1 Algorithme “Pas de bébé et pas de géant”
3.1.1 Algorithme
3.1.2 Exemple
3.2 Algorithme original de Schoof
3.2.1 Algorithme
3.2.2 Exemple
3.3 Premières optimisations d’Atkin
3.3.1 Action du Frobenius sur E[ℓ]
3.3.2 Équations modulaires
3.3.3 Algorithme
3.3.4 Exemple
3.4 Idées d’Elkies et ses développements
3.4.1 Principe
3.4.2 Courbes isogènes et isogénies
3.4.3 Cycle d’isogénies
3.4.4 Exemple
II Calculs d’isogénie entre courbes elliptiques 
4 Algorithmes en grande caractéristique 
4.1 Formules de Vélu
4.1.1 Corps algébriquement clos
4.1.2 Reformulation dans un corps fini
4.1.3 Isogénies de degré 2 sur un corps fini
4.2 Calcul d’isogénie en grande caractéristique
4.2.1 Cas de C
4.2.2 Application aux corps finis
4.3 Résultats
5 Premier algorithme de Couveignes en petite caractéristique 
5.1 Prérequis
5.1.1 Points de p-torsion
5.1.2 Groupe formel
5.2 Description théorique de l’algorithme
5.2.1 Morphismes de groupe formel
5.2.2 Conditions nécessaires vérifiées par un morphisme
5.2.3 Énumérations
5.3 Mise en œuvre pratique de l’algorithme
5.3.1 Calculs incrémentaux avec des séries tronquées
5.3.2 Programmation efficace de l’algorithme
5.4 Résultats
5.4.1 Exemples
5.4.2 Statistiques
6 Deuxième algorithme de Couveignes en petite caractéristique 
6.1 Principe de l’algorithme
6.1.1 Propriétés des points de pk-torsion
6.1.2 Algorithme
6.2 Points de pk-torsion
6.2.1 Constructions de Ea[pk]
6.2.2 Algorithme “naturel”
6.2.3 Deuxième algorithme
6.2.4 Efficacité des deux approches
6.3 Isomorphismes entre Ea[pk] et Eb[pk]
6.3.1 Isomorphismes entre extensions d’Artin-Shreier
6.3.2 Résoudre Xp − X = δ dans une tour d’extensions d’Artin-Schreier
6.4 Résultats
6.4.1 Exemple
6.4.2 Quelques temps de calcul
7 Algorithme en caractéristique deux 
7.1 Isogénies définies sur F2n
7.1.1 Point de 2-torsion
7.1.2 Caractérisation des isogénies
7.2 Algorithmes
7.2.1 Système linéaire défini sur F2n
7.2.2 Système quadratique défini sur F2
7.2.3 Améliorations pratiques
7.3 Résultats
8 Combinaison d’algorithmes en caractéristique impaire 
8.1 Isogénies et points de 2-torsion
8.1.1 Caractérisation
8.1.2 Application
8.2 Connexion entre petite et grande caractéristique
8.2.1 Principe
8.2.2 Algorithme générique
8.2.3 Exploiter les formules de Vélu
8.3 Exemple
III Implantation efficace et résultats 
9 Plus grand diviseur commun de deux entiers 
9.1 Algorithmes de pgcd simples
9.1.1 pgcd euclidiens
9.1.2 pgcd binaires
9.1.3 Bilan
9.2 Algorithmes de pgcd étendus
9.2.1 Algorithme de Lehmer
9.2.2 Algorithmes binaire et plus-minus
9.2.3 Algorithme binaire généralisé
9.3 Résultats
9.3.1 pgcd simples
9.3.2 pgcd étendus
10 Corps finis et programmation 
10.1 Librairie de programmation ZEN
10.1.1 Trois principes fondateurs
10.1.2 Utilisation
10.2 Exponentiation
10.2.1 Chaîne d’addition
10.2.2 Chaîne d’addition-soustraction
10.2.3 Résultats
11 Quelques perfectionnements à l’algorithme SEA 
11.1 Optimisations de l’algorithme de Schoof
11.1.1 Factorisation des équations modulaires
11.1.2 Algorithme d’Elkies
11.1.3 Algorithme de Schoof
11.2 Algorithmes “tri-recherche”
11.2.1 Préparation des données
11.2.2 Algorithme d’Atkin
11.2.3 Variante du “tri-recherche” d’Atkin
12 Programmation de l’algorithme SEA et résultats 
12.1 Implantation
12.1.1 Algorithmes utilisés
12.1.2 Stratégie statique
12.1.3 Stratégie dynamique
12.2 Résultats
12.2.1 Corps de taille moyenne
12.2.2 Corps de grande taille
12.3 Application à la cryptographie
12.3.1 Stratégie “Early abort”
12.3.2 Résultats
A Exemple d’exécution du programme SEA
Bibliographie

Télécharger le rapport complet