Algorithme de Schoof

L'algorithme de Schoof est un algorithme efficace pour compter les points de courbes elliptiques sur les corps finis. Il a des applications en cryptographie sur les courbes elliptiques, où il est utilisé pour construire des courbes elliptiques ayant un cardinal divisible par un grand nombre premier.

L'algorithme a été publié par René Schoof en 1985, ce qui a constitué une avancée majeure, s'agissant du premier algorithme déterministe polynomial pour le comptage de points. Avant cet algorithme, seules des méthodes de complexité exponentielle étaient connues pour ce problème, tels l'algorithme naïf et l'algorithme pas de bébé pas de géant.

Introduction modifier

Soit   une courbe elliptique définie sur le corps fini  , où   avec   un nombre premier et   un entier  . Supposant  , une courbe elliptique peut être exprimée par l'équation de Weierstrass (simplifiée)

 

avec  . L'ensemble   des points définis sur   est formé par les solutions   qui satisfont l'équation de Weierstrass, et un point à l'infini  . La loi de groupe de   restreinte à cet ensemble donne une structure de groupe abélien à  , avec   pour élément neutre. Le problème du comptage des points consiste à calculer la cardinalité de  . L'algorithme de Schoof's pour calculer la cardinalité   combine le théorème de Hasse sur les courbes elliptiques avec le théorème des restes chinois et les polynômes de division.

Théorème de Hasse modifier

Soit   une courbe elliptique définie sur le corps fini  , son groupe de points   satisfait

 

Ce résultat, énoncé par Helmut Hasse en 1934, restreint l'espace de recherche à un ensemble fini, bien que large, de possibilités. En définissant  , et en faisant appel à ce théorème, calculer la valeur de   modulo   avec   suffit à déterminer  , et ainsi  . Bien qu'on ne connaisse pas de méthode efficace pour calculer   directement pour un   quelconque, il est possible de calculer   pour un petit premier   efficacement. En choisissant un ensemble de nombres premiers   tels que  , et en calculant   pour tout  , le théorème des restes chinois permet de calculer  .

Pour calculer   pour un nombre premier  , l'algorithme s'appuie sur les propriétés de l'endomorphisme de Frobenius   et des polynômes de division.

Endomorphisme de Frobenius modifier

Soit   définie sur  , on considère les points de   dans la clôture algébrique   de  , c'est-à-dire les points à coordonnées dans  . L'automorphisme de Frobenius de   sur   s'étend en un endomorphisme de la courbe elliptique par   et  . Ce morphisme agit comme l'identité sur  , et on vérifie qu'il est un morphisme de groupes de   vers lui-même. L'endomorphisme de Frobenius satisfait un polynôme quadratique, lié à la cardinalité de   par le théorème suivant:

Théorème — L'endomorphisme de Frobenius   satisfait l'équation caractéristique

  

Par conséquent, pour tout   on a  , où on a noté   l'addition de la courbe elliptique et   et   la multiplication scalaire de   par   et de   par  .

On pourrait imaginer de calculer  ,   et   comme des fonctions dans l'anneau des coordonnées   de  , et ensuite de chercher la valeur   qui satisfait l'équation, mais la croissance des degrés des polynômes en jeu donnerait un algorithme de complexité exponentielle. L'idée de Schoof consiste à faire ce même calcul en se restreignant aux points d'ordre   pour plusieurs petits premiers  .

Pour un premier   fixé, différent de 2 et  , il faut donc déterminer la valeur de  . Soit   un point appartenant au groupe de  -torsion  , alors  , où   est le seul entier tel que   et  . Puisque   est un morphisme de groupes injectif,   à le même ordre que  , alors pour   dans  , on a aussi   si  . Le problème se réduit alors à résoudre l'équation

 

  et   sont des entiers dans l'intervalle  .

Calcul modulo un petit premier modifier

Par définition, le  -ième polynôme de division   a pour racines les abscisses des points d'ordre  . Alors calculer le polynôme   restreint aux points de  -torsion revient à faire les calculs dans l'anneau des coordonnées de   modulo le  -ième polynôme de division, c'est-à-dire dans l'anneau  . En particulier, le degré de   et   dans   est au plus 1 en   et au plus   en  .

La multiplication scalaire   se calcule soit par exponentiation rapide, soit par la formule suivante

 

  est le  -ième polynôme de division. On remarque que   est une fonction en   uniquement, et on la note  .

Il y a alors deux cas: soit  , soit  . On rappelle que ces égalités sont calculées modulo  .

Premier cas (xq2, yq2) ≠ ± q̅ (x, y) modifier

Par la loi de groupe de   on a:

 

L'équation sur l'abscisse   permet alors de restreindre le choix à deux possibilités pour  , l'une l'opposée de l'autre. Ensuite l'ordonnée   permet de conclure.

On commence par montrer que   est une fonction du seul  . On considère  , puisque   est pair, remplacer   par   donne

 

et on conclut que

 

Maintenant, si   pour un  , alors   satisfait

 

pour tous les points   de  -torsion.

Comme dit auparavant, les valeurs de   et   permettent de conclure lequel parmi   et   vérifie l'équation, donnant ainsi la valeur de  .

Deuxième cas (xq2, yq2) = ± q (x, y) modifier

On commence par le cas  . Puisque   est impair, on ne peut pas avoir  , et donc  . L'équation caractéristique donne  , par conséquent  . Ceci implique que   est un carré modulo  . Soit  , il suffit maintenant de calculer   dans   et de vérifier que  . Dans ce cas   est égal à   selon la valeur de l'ordonnée.

Si   n'est pas un carré modulo  , ou si l'équation n'est vérifiée ni pour  , ni pour  , l'hypothèse   est fausse, et donc  . L'équation caractéristique permet alors de conclure que  .

Cas additionnel ℓ = 2 modifier

L'exposition qui précède avait exclu le cas  , qui doit être traité à part. Puisqu'on suppose que   est impair,   et en particulier,   si et seulement si   a un point d'ordre 2. Par définition, tout élément d'ordre 2 est de la forme  . Alors   si et seulement si   a une racine dans  , si et seulement si  .

Algorithme modifier

(1) Choisir un ensemble de premiers  , ne contenant pas   tel que  
(2) Poser   si  , sinon poser  .
(4) Pour tout  :
(a) Calculer le polynôme de division  . Tous les calculs qui suivent se font dans l'anneau  
(b) Soit   le seul entier tel que   et  .
(c) Calculer  ,   et   .
(d) si   alors
(i) Calculer  .
(ii) Pour tout  :
(iii) si   alors
(iv) si   alors  ; sinon  .
(e) sinon, si   est un carré modulo   alors
(i) calculer   tel que  
(ii) calculer  
(iii) si   alors  
(iv) sinon, si   alors  
(v) sinon  
(f) sinon  
(5) Utiliser le Théorème des restes chinois pour calculer   modulo  .

On remarque que, puisque   a été choisi tel que  , le théorème de Hasse permet de déduire   et  .

Complexité modifier

Le calcul le plus coûteux est l'évaluation de   et  , pour chaque premier  , c'est-à-dire le calcul de  ,  ,  ,   pour tout  . Ceci requiert des exponentiations dans l'anneau   et demande   multiplications. Comme le degré de   est  , chaque élément de l'anneau est un polynôme de degré  . Par le théorème des nombres premiers, il y a environ   premiers de taille  , ce qui implique que tous les   sont dans   et donc  . Par conséquent chaque multiplication dans l'anneau   demande   multiplications dans  , chaque multiplication nécessitant de   opérations. Au total, le nombre d'opérations binaires pour chaque premier   est  . Puisqu'il faut répéter ce calcul pour chacun des   premiers, la complexité de l'algorithme de Schoof est de   opérations binaires. Les techniques de multiplication rapide d'entiers et de polynômes réduit cette complexité à  .

Améliorations de l'algorithme de Schoof modifier

Dans les années '90, A. O. L. Atkin et puis Noam Elkies, ont proposé des améliorations à l'algorithme original de Schoof en restreignant l'ensemble   de premiers pris en considération. Ces premiers ont par la suite été appelés respectivement premiers de Atkin et de Elkies. Un premier   est dit d'Elkies si l'équation caractéristique du Frobenius   se scinde dans  , il est dit un premier d'Atkin sinon. Atkin a montré comment combiner l'information obtenue par les premiers d'Atkin avec celle obtenue par ceux d'Elkies afin de concevoir un algorithme efficace, appelé algorithme de Schoof–Elkies–Atkin (ou SEA). Le premier problème dans cet algorithme consiste à déterminer si un premier donné   et d'Elkies ou d'Atkin. À cette fin, on étudie les propriétés de factorisation du polynôme modulaire, un objet dérivé de la théorie des formes modulaires et des courbes elliptiques sur les complexes.

Une fois déterminé le type de premier, la complexité optimale pour l'algorithme SEA est obtenue en travaillant uniquement avec les premiers d'Elkies. Dans ce cas, en effet, il est possible de remplacer les polynômes de division par des polynômes de degré plus petit:   plutôt que  . Pour une réalisation efficace, il est nécessaire d'utiliser des algorithmes probabilistes pour la factorisation de polynômes, ce qui fait de l'algorithme SEA un algorithme de Las Vegas. Sous l'hypothèse heuristique qu'environ la moitié des nombres premiers jusqu'à une borne de   sont des premiers d'Elkies, ceci donne un algorithme plus efficace que l'algorithme de Schoof, d'une complexité moyenne de   en utilisant une arithmétique naïve, ou de   avec une arithmétique rapide.

Implémentations modifier

Il existe des nombreuses implémentations de l'algorithme de Schoof et de SEA.

  • Le logiciel de calcul formel PARI/GP contient une implémentation de SEA pour les corps premiers[1].
  • Le logiciel Magma (logiciel) contient une implémentation de SEA pour tout corps fini[2].
  • Mike Scott a mis dans le domaine public une implémentation en C++ [3] de l'algorithme de Schoof sur les corps premiers et les corps quadratiques. Le logiciel dépend de la bibliothèque MIRACL, distribuée sous la licence AGPLv3.

Voir aussi modifier

Références modifier

  • (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Schoof's algorithm » (voir la liste des auteurs).
  • R. Schoof: Elliptic Curves over Finite Fields and the Computation of Square Roots mod p. Math. Comp., 44(170):483–494, 1985. Available at http://www.mat.uniroma2.it/~schoof/ctpts.pdf
  • R. Schoof: Counting Points on Elliptic Curves over Finite Fields. J. Theor. Nombres Bordeaux 7:219–254, 1995. Available at http://www.mat.uniroma2.it/~schoof/ctg.pdf
  • G. Musiker: Schoof's Algorithm for Counting Points on  . Available at http://www.math.umn.edu/~musiker/schoof.pdf
  • V. Müller : Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern. Master's Thesis. Universität des Saarlandes, Saarbrücken, 1991. Available at http://lecturer.ukdw.ac.id/vmueller/publications.php
  • A. Enge: Elliptic Curves and their Applications to Cryptography: An Introduction. Kluwer Academic Publishers, Dordrecht, 1999.
  • L. C. Washington: Elliptic Curves: Number Theory and Cryptography. Chapman & Hall/CRC, New York, 2003.
  • N. Koblitz: A Course in Number Theory and Cryptography, Graduate Texts in Math. No. 114, Springer-Verlag, 1987. Second edition, 1994