Algorithme de Schoof

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

${\displaystyle y^{2}=x^{3}+Ax+B\,}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1) Choisir un ensemble de premiers ${\displaystyle S}$, ne contenant pas ${\displaystyle p}$ tel que ${\displaystyle N=\prod _{\ell \in S}\ell >4{\sqrt {q}}.}$

(2) Poser ${\displaystyle t_{2}=0}$ si ${\displaystyle \gcd(x^{q}-x,x^{3}+Ax+B)\neq 1}$, sinon poser ${\displaystyle t_{2}=1}$.

(4) Pour tout ${\displaystyle \ell \in S}$:

(a) Calculer le polynôme de division ${\displaystyle \psi _{\ell }}$. Tous les calculs qui suivent se font dans l'anneau ${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{\ell }).}$

(b) Soit ${\displaystyle {\bar {q}}}$ le seul entier tel que ${\displaystyle q\equiv {\bar {q}}{\pmod {\ell }}}$ et ${\displaystyle \mid {\bar {q}}\mid <\ell /2}$.

(c) Calculer ${\displaystyle (x^{q},y^{q})}$, ${\displaystyle (x^{q^{2}},y^{q^{2}})}$ et ${\displaystyle (x_{\bar {q}},y_{\bar {q}})}$ .

(d) si ${\displaystyle x^{q^{2}}\neq x_{\bar {q}}}$ alors

(i) Calculer ${\displaystyle (X,Y)}$.

(ii) Pour tout ${\displaystyle 1\leq {\bar {t}}\leq (\ell -1)/2}$:

(iii) si ${\displaystyle X=x_{\bar {t}}^{q}}$ alors

(iv) si ${\displaystyle Y=y_{\bar {t}}^{q}}$ alors ${\displaystyle t_{\ell }={\bar {t}}}$; sinon ${\displaystyle t_{\ell }=-{\bar {t}}}$.

(e) sinon, si ${\displaystyle q}$ est un carré modulo ${\displaystyle \ell }$ alors

(i) calculer ${\displaystyle w}$ tel que ${\displaystyle q\equiv w^{2}{\pmod {\ell }}}$

(ii) calculer ${\displaystyle w(x^{q},y^{q})}$

(iii) si ${\displaystyle w(x^{q},y^{q})=(x^{q^{2}},y^{q^{2}})}$ alors ${\displaystyle t_{\ell }=2w}$

(iv) sinon, si ${\displaystyle w(x^{q},y^{q})=(x^{q^{2}},-y^{q^{2}})}$ alors ${\displaystyle t_{\ell }=-2w}$

(v) sinon ${\displaystyle t_{\ell }=0}$

(f) sinon ${\displaystyle t_{\ell }=0}$

(5) Utiliser le Théorème des restes chinois pour calculer ${\displaystyle t}$ modulo ${\displaystyle N}$.

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

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

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 ${\displaystyle 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 ${\displaystyle \ell }$ est dit d'Elkies si l'équation caractéristique du Frobenius ${\displaystyle \phi ^{2}-t\phi +q=0}$ se scinde dans ${\displaystyle \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é ${\displaystyle \ell }$ 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: ${\displaystyle O(\ell )}$ plutôt que ${\displaystyle 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é des nombres premiers jusqu'à une borne de ${\displaystyle O(\log q)}$ sont des premiers d'Elkies, ceci donne un algorithme plus efficace que l'algorithme de Schoof, d'une complexité moyenne de ${\displaystyle O(\log ^{6}q)}$ en utilisant une arithmétique naïve, ou de ${\displaystyle {\tilde {O}}(\log ^{4}q)}$ avec une arithmétique rapide.

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.

• Cryptographie sur les courbes elliptiques
• Endomorphisme de Frobenius
• Théorème des restes chinois

• (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 ${\displaystyle 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