Algorithme de Schoof

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 grand nombre un 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 | modifier le code]

Soit E une courbe elliptique définie sur le corps fini \mathbb{F}_q, où q=p^n avec p un nombre premier et n un entier \geq 1. Supposant p\neq 2, 3, une courbe elliptique peut être exprimée par l'équation de Weierstrass (simplifiée)


y^2 = x^3 + Ax + B \,

avec A,B\in \mathbb{F}_{q}. L'ensemble E(\mathbb{F}_q) des points définis sur \mathbb{F}_{q} est formé par les solutions (a,b)\in\mathbb{F}_{q}^2 qui satisfont l'équation de Weierstrass, et un point à l'infini O. La loi de groupe de E restreinte à cet ensemble donne une structure de groupe abélien à E(\mathbb{F}_q), avec O pour élément neutre. Le problème du comptage des points consiste à calculer la cardinalité de E(\mathbb{F}_{q}). L'algorithme de Schoof's pour calculer la cardinalité \sharp E(\mathbb{F}_{q}) 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 | modifier le code]

Article général Pour un article plus général, voir théorème de Hasse sur les courbes elliptiques.

Soit E/\mathbb{F}_{q} une courbe elliptique définie sur le corps fini \mathbb{F}_{q}, son groupe de points \sharp E(\mathbb{F}_q) satisfait


\mid q + 1 - \sharp E(\mathbb{F}_{q}) \mid \leq 2\sqrt{q}.

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 t=q + 1 - \sharp E(\mathbb{F}_{q}), et en faisant appel à ce théorème, calculer la valeur de t modulo N avec N > 4\sqrt{q} suffit à déterminer t, et ainsi \sharp E(\mathbb{F}_{q}). Bien qu'on ne connaisse pas de méthode efficace pour calculer t \pmod N directement pour un N quelconque, il est possible de calculer t  \pmod \ell pour un petit premier \ell efficacement. En choisissant un ensemble de nombres premiers S=\{\ell_1,\ell_2,...,\ell_r\} tels que \prod \ell_i = N > 4\sqrt{q}, et en calculant t \pmod {\ell_i} pour tout \ell_i\in S, le théorème des restes chinois permet de calculer t \pmod N.

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

Endomorphisme de Frobenius[modifier | modifier le code]

Soit E définie sur \mathbb{F}_{q}, on considère les points de E dans la clôture algébrique \bar{\mathbb{F}}_{q} de \mathbb{F}_{q}, c'est-à-dire les points à coordonnées dans \bar{\mathbb{F}}_{q}. L'automorphisme de Frobenius de \bar{\mathbb{F}}_{q} sur \mathbb{F}_q s'étend en un endomorphisme de la courbe elliptique par  \phi : (x, y) \mapsto (x^{q}, y^{q}) et \phi: O\mapsto O. Ce morphisme agit comme l'identité sur E(\mathbb{F}_{q}), et on vérifie qu'il est un morphisme de groupes de E(\bar{\mathbb{F}_{q}}) vers lui même. L'endomorphisme de Frobenius satisfait un polynôme quadratique, lié à la cardinalité de E(\mathbb{F}_{q}) par le théorème suivant:

Théorème: L'endomorphisme de Frobenius \phi satisfait l'équation caractéristique

  \phi ^2 - t\phi + q = 0, t = q + 1 - \sharp E(\mathbb{F}_q)

Par conséquent, pour tout P=(x, y) \in E on a (x^{q^{2}}, y^{q^{2}} ) + q(x, y) = t(x^{q}, y^{q}), où on a noté + l'addition de la courbe elliptique et q(x,y) et t(x^{q},y^{q}) la multiplication scalaire de (x,y) par q et de (x^{q},y^{q}) par t.

On pourrait imaginer de calculer (x^{q^{2}}, y^{q^{2}}), (x^{q}, y^{q}) et q(x, y) comme des fonctions dans l'anneau des coordonnées \mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B) de E, et ensuite de chercher la valeur t 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 \ell pour plusieurs petits premiers \ell.

Pour un premier \ell fixé, différent de 2 et p, il faut donc déterminer la valeur de t \pmod \ell. Soit (x, y) un point appartenant au groupe de \ell-torsion E[\ell]=\{P\in E(\bar{\mathbb{F}_{q}}) \mid \ell P=O \}, alors qP = \bar{q}P, où \bar{q} est le seul entier tel que q \equiv \bar{q}  \pmod \ell et \mid \bar{q} \mid< \ell/2. Puisque \phi est un morphisme de groupes injectif, \phi (P) à le même ordre que P, alors pour (x, y) dans E[\ell], on a aussi t(x^{q}, y^{q})= \bar{t}(x^{q}, y^{q}) si t \equiv \bar{t}  \pmod \ell. Le problème se réduit alors à résoudre l'équation

  (x^{q^{2}}, y^{q^{2}}) + \bar{q}(x, y) \equiv \bar{t}(x^{q}, y^{q}),

\bar{t} et \bar{q} sont des entiers dans l'intervalle [-(l-1)/2,(l-1)/2].

Calcul modulo un petit premier[modifier | modifier le code]

Par définition, le \ell-ième polynôme de division \psi_{\ell} a pour racines les abscisses des points d'ordre \ell. Alors calculer le polynôme (x^{q^{2}}, y^{q^{2}}) + \bar{q}(x, y) restreint aux points de \ell-torsion revient à faire les calculs dans l'anneau des coordonnées de E modulo le \ell-ième polynôme de division, c'est-à-dire dans l'anneau \mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B, \psi_{\ell}). En particulier, le degré de X et Y dans (X(x,y),Y(x,y)):=(x^{q^{2}}, y^{q^{2}}) + \bar{q}(x, y) est au plus 1 en y et au plus (\ell^2-3)/2 en x.

La multiplication scalaire \bar{q}(x, y) se calcule soit par exponentiation rapide, soit par la formule suivante

 
\bar{q} (x,y) = (x_{\bar{q}},y_{\bar{q}}) = \left( x - \frac {\psi_{\bar{q}-1} \psi_{\bar{q}+1}}{\psi^{2}_{\bar{q}}}, \frac{\psi_{2\bar{q}}}{2\psi^{4}_{\bar{q}}} \right)

\psi_{n} est le n-ième polynôme de division. On remarque que y_{\bar{q}}/y est une fonction en x uniquement, et on la note \theta(x).

Il y a alors deux cas: soit (x^{q^{2}}, y^{q^{2}}) \neq \pm \bar{q}(x, y), soit (x^{q^{2}}, y^{q^{2}}) = \pm \bar{q}(x, y). On rappelle que ces égalités sont calculées modulo \psi_\ell.

Premier cas (x^{q^{2}}, y^{q^{2}}) \neq \pm \bar{q}(x, y)[modifier | modifier le code]

Par la loi de groupe de E(\mathbb{F}_{q}) on a:


X(x,y) = \left( \frac{y^{q^{2}} - y_{\bar{q}}}{x^{q^{2}} - x_{\bar{q}}} \right) ^{2} - x^{q^{2}} - x_{\bar{q}}.

L'équation sur l'abscisse x permet alors de restreindre le choix à deux possibilités pour \bar{t}, l'une l'opposée de l'autre. Ensuite l'ordonnée y permet de conclure.

On commence par montrer que X est une fonction du seul x. On considère (y^{q^{2}} - y_{\bar{q}})^{2}=y^{2}(y^{q^{2}-1}-y_{\bar{q}}/y)^{2}, puisque q^{2}-1 est pair, remplacer y^{2} par x^3+Ax+B donne


(x^3+Ax+B)((x^3+Ax+B)^{\frac{q^{2}-1}{2}}-\theta(x))

et on conclut que


X(x)\equiv (x^3+Ax+B)((x^3+Ax+B)^{\frac{q^{2}-1}{2}}-\theta(x))\bmod \psi_\ell(x).

Maintenant, si X \equiv x^{q} _ {\bar{t}}\bmod \psi_l(x) pour un \bar{t}\in [0,(\ell-1)/2], alors \bar{t} satisfait


\phi ^{2}(P) \mp \bar{t} \phi(P) + \bar{q}P = O

pour tous les points P de \ell-torsion.

Comme dit auparavant, les valeurs de Y et y_{\bar{t}}^{q} permettent de conclure lequel parmi \bar{t} et -\bar{t} vérifie l'équation, donnant ainsi la valeur de t\equiv \bar{t}\pmod \ell.

Deuxième cas (x^{q^{2}}, y^{q^{2}}) = \pm q(x, y)[modifier | modifier le code]

On commence par le cas (x^{q^{2}}, y^{q^{2}}) = \bar{q}(x, y). Puisque \ell est impair, on ne peut pas avoir \bar{q}(x, y)=-\bar{q}(x, y), et donc \bar{t}\neq 0. L'équation caractéristique donne \bar{t} \phi(P) = 2\bar{q} P, par conséquent \bar{t}^{2}\bar{q} \equiv (2q)^{2}  \pmod \ell. Ceci implique que q est un carré modulo \ell. Soit q \equiv w^{2}  \pmod \ell, il suffit maintenant de calculer w\phi(x,y) dans \mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B, \psi_{\ell}) et de vérifier que \bar{q}(x, y)=w\phi(x,y). Dans ce cas t_{\ell} est égal à \pm 2w \pmod \ell selon la valeur de l'ordonnée.

Si q n'est pas un carré modulo \ell, ou si l'équation n'est vérifiée ni pour w, ni pour -w, l'hypothèse (x^{q^{2}}, y^{q^{2}}) = +\bar{q}(x, y) est fausse, et donc (x^{q^{2}}, y^{q^{2}}) = - \bar{q}(x, y). L'équation caractéristique permet alors de conclure que t_\ell=0.

Cas additionnel \ell = 2[modifier | modifier le code]

L'exposition qui précède avait exclu le cas \ell = 2, qui doit être traité à part. Puisque on suppose que q est impair, q + 1 - t  \equiv  t \pmod  2 et en particulier, t_{2} \equiv 0  \pmod 2 si et seulement si E(\mathbb{F}_{q}) a un point d'ordre 2. Par définition, tout élément d'ordre 2 est de la forme (x_{0}, 0). Alors t_{2} \equiv 0  \pmod 2 si et seulement si x^{3} + Ax + B a une racine dans \mathbb{F}_{q}, si et seulement si \gcd(x^{q}-x, x^{3} + Ax + B)\neq 1.

Algorithme[modifier | modifier le code]

(1) Choisir un ensemble de premiers S, ne contenant pas p tel que N=\prod_{\ell \in S} \ell > 4\sqrt{q}.
(2) Poser t_2=0 si \gcd(x^{q}-x, x^{3} + Ax + B)\neq 1, sinon poser t_2=1.
(4) Pour tout \ell \in S:
(a) Calculer le polynôme de division \psi_\ell. Tous les calculs qui suivent se font dans l'anneau \mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B, \psi_{\ell}).
(b) Soit \bar{q} le seul entier tel que q \equiv \bar{q}  \pmod \ell et \mid \bar{q} \mid< \ell/2.
(c) Calculer (x^{q}, y^{q}), (x^{q^{2}}, y^{q^{2}}) et (x_{\bar{q}},y_{\bar{q}}) .
(d) si x^{q^{2}}\neq x_{\bar{q}} alors
(i) Calculer (X,Y) .
(ii) Pour tout 1\leq \bar{t} \leq (\ell-1)/2:
(iii) si X = x^{q} _ {\bar{t}} alors
(iv) si Y = y^{q} _ {\bar{t}} alors t_{\ell}=\bar{t}; sinon t_{\ell}=-\bar{t}.
(d) sinon, si q est un carré modulo \ell alors
(i) calculer w tel que q\equiv w^{2} \pmod \ell
(ii) calculer w(x^{q}, y^{q})
(iii) si w(x^{q}, y^{q})=(x^{q^{2}}, y^{q^{2}}) alors t_\ell=2w
(iv) sinon, si w(x^{q}, y^{q})=(x^{q^{2}}, -y^{q^{2}}) alors t_\ell=-2w
(v) sinon t_{\ell}=0
(e) sinon t_{\ell}=0
(5) Utiliser le Théorème des restes chinois pour calculer t modulo N.

On remarque que, puisque S a été choisi tel que N>4\sqrt{q}, le théorème de Hasse permet de déduire t et  \sharp E(\mathbb{F}_{q}) = q+1-t.

Complexité[modifier | modifier le code]

Le calcul le plus coûteux est l'évaluation de \phi(P) et \phi^{2}(P), pour chaque premier \ell, c'est-à-dire le calcul de x^q, y^q, x^{q^2}, y^{q^2} pour tout \ell. Ceci requiert des exponentiations dans l'anneau R = \mathbb{F}_{q}[x, y]/ (y^2-x^3-Ax-B, \psi_\ell) et demande O(\log q) multiplications. Comme le degré de \psi_\ell est \frac{\ell^2-1}{2}, chaque élément de l'anneau est un polynôme de degré O(\ell^2). Par le théorème des nombres premiers, il y a environ O(\log q) premiers de taille O(\log q), ce qui implique que tous les \ell sont dans O(\log q) et donc O(\ell^2) = O(\log^2q). Par conséquent chaque multiplication dans l'anneau R demande O(\log^4 q) multiplications dans \mathbb{F}_{q}, chaque multiplication nécessitant de O(\log^2 q) opérations. Au total, le nombre d'opérations binaires pour chaque premier \ell est O(\log^7 q). Puisque il faut répéter ce calcul pour chacun des O(\log q) premiers, la complexité de l'algorithme de Schoof est de O(\log^8 q) opérations binaires. Les techniques de multiplication rapide d'entiers et de polynômes réduit cette complexité à \tilde{O}(\log^5 q).

Améliorations de l'algorithme de Schoof[modifier | modifier le code]

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 S =  \{\ell_1, \ldots, \ell_s\} de premiers pris en considération. Ces premiers ont par la suite été appelés respectivement premiers de Atkin et de Elkies. Un premier \ell est dit d'Elkies si l'équation caractéristique du Frobenius \phi^2-t\phi+ q = 0 se scinde dans \mathbb{F}_\ell, 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é \ell et d'Elkies ou d'Atkin. À ce 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: O(\ell) plutôt que O(\ell^2). 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és des nombres premiers jusqu'à une borne de O(\log q) sont des premiers d'Elkies, ceci donne un algorithme plus efficace que l'algorithme de Schoof, d'une complexité moyenne de O(\log^6 q) en utilisant une arithmétique naïve, ou de \tilde{O}(\log^4 q) avec une arithmétique rapide. Il est à remarquer que cette hypothèse heuristique est prouvablement vérifiée pour la plus part des courbes elliptiques, mais il est inconnu si elle est vraie en générale, même en supposant l'hypothèse de Riemann généralisée.

Implantations[modifier | modifier le code]

Il existe des nombreuses implantations de l'algorithme de Schoof et de SEA.

  • Le logiciel de calcul formel PARI/GP contient une implantation de SEA pour les corps premiers[1].
  • Le logiciel Magma (logiciel) contient une implantation de SEA pour tout corps fini[2].
  • Mike Scott a mis dans le domaine publique une implantation 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 | modifier le code]

Références[modifier | modifier le code]

  • (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 E(\mathbb{F}_{q}). 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