Algorithme de Schoof

LModèle:'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

Soit $E$ une courbe elliptique définie sur le corps fini ${𝔽}_q$, où $q=p^n$ avec $p$ un nombre premier et $n$ un entier $\ge 1$. Supposant $p\ne 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 {𝔽}_q$. L'ensemble $E({𝔽}_q)$ des points définis sur ${𝔽}_q$ est formé par les solutions $(a,b)\in {𝔽}_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({𝔽}_q)$, avec $O$ pour élément neutre. Le problème du comptage des points consiste à calculer la cardinalité de $E({𝔽}_q)$. L'algorithme de Schoof's pour calculer la cardinalité $\mathrm{♯}E({𝔽}_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

Modèle:Article général Soit $E/{𝔽}_q$ une courbe elliptique définie sur le corps fini ${𝔽}_q$, son groupe de points $\mathrm{♯}E({𝔽}_q)$ satisfait

$\mid q+1-\mathrm{♯}E({𝔽}_q)\mid \le 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-\mathrm{♯}E({𝔽}_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 $\mathrm{♯}E({𝔽}_q)$. Bien qu'on ne connaisse pas de méthode efficace pour calculer $t(\mathrm{mod}N)$ directement pour un $N$ quelconque, il est possible de calculer $t(\mathrm{mod}\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(\mathrm{mod}{\ell }_i)$ pour tout ${\ell }_i\in S$, le théorème des restes chinois permet de calculer $t(\mathrm{mod}N)$.

Pour calculer $t(\mathrm{mod}\ell )$ pour un nombre premier $\ell \ne p$, l'algorithme s'appuie sur les propriétés de l'endomorphisme de Frobenius $\varphi$ et des polynômes de division.

Endomorphisme de Frobenius

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

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 ${𝔽}_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(\mathrm{mod}\ell )$. Soit $(x,y)$ un point appartenant au groupe de $\ell$-torsion $E[\ell ]=\{P\in E(\overline{{𝔽}_q})\mid \ell P=O\}$, alors $qP=\overline{q}P$, où $\overline{q}$ est le seul entier tel que $q\equiv \overline{q}(\mathrm{mod}\ell )$ et $\mid \overline{q}\mid <\ell /2$. Puisque $\varphi$ est un morphisme de groupes injectif, $\varphi (P)$ à le même ordre que $P$, alors pour $(x,y)$ dans $E[\ell ]$, on a aussi $t(x^q,y^q)=\overline{t}(x^q,y^q)$ si $t\equiv \overline{t}(\mathrm{mod}\ell )$. Le problème se réduit alors à résoudre l'équation

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

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

Calcul modulo un petit premier

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})+\overline{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 ${𝔽}_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})+\overline{q}(x,y)$ est au plus 1 en $y$ et au plus $({\ell }^2-3)/2$ en $x$.

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

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

où ${\psi }_n$ est le $n$-ième polynôme de division. On remarque que $y_{\overline{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})\ne \pm \overline{q}(x,y)$, soit $(x^{q^2},y^{q^2})=\pm \overline{q}(x,y)$. On rappelle que ces égalités sont calculées modulo ${\psi }_{\ell }$.

Premier cas Modèle:Math

Par la loi de groupe de $E({𝔽}_q)$ on a:

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

L'équation sur l'abscisse $x$ permet alors de restreindre le choix à deux possibilités pour $\overline{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_{\overline{q}}{)}^2=y^2(y^{q^2-1}-y_{\overline{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)){mod\psi }_{\ell }(x).$

Maintenant, si $X\equiv x_{\overline{t}}^q{mod\psi }_l(x)$ pour un $\overline{t}\in [0,(\ell -1)/2]$, alors $\overline{t}$ satisfait

${\varphi }^2(P)\mp \overline{t}\varphi (P)+\overline{q}P=O$

pour tous les points $P$ de $\ell$-torsion.

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

Deuxième cas Modèle:Math

On commence par le cas $(x^{q^2},y^{q^2})=\overline{q}(x,y)$. Puisque $\ell$ est impair, on ne peut pas avoir $\overline{q}(x,y)=-\overline{q}(x,y)$, et donc $\overline{t}\ne 0$. L'équation caractéristique donne $\overline{t}\varphi (P)=2\overline{q}P$, par conséquent ${\overline{t}}^2\overline{q}\equiv (2q{)}^2(\mathrm{mod}\ell )$. Ceci implique que $q$ est un carré modulo $\ell$. Soit $q\equiv w^2(\mathrm{mod}\ell )$, il suffit maintenant de calculer $w\varphi (x,y)$ dans ${𝔽}_q[x,y]/(y^2-x^3-Ax-B,{\psi }_{\ell })$ et de vérifier que $\overline{q}(x,y)=w\varphi (x,y)$. Dans ce cas $t_{\ell }$ est égal à $\pm 2w(\mathrm{mod}\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})=+\overline{q}(x,y)$ est fausse, et donc $(x^{q^2},y^{q^2})=-\overline{q}(x,y)$. L'équation caractéristique permet alors de conclure que $t_{\ell }=0$.

Cas additionnel Modèle:Math

L'exposition qui précède avait exclu le cas $\ell =2$, qui doit être traité à part. Puisqu'on suppose que $q$ est impair, $q+1-t\equiv t(\mathrm{mod}2)$ et en particulier, $t_2\equiv 0(\mathrm{mod}2)$ si et seulement si $E({𝔽}_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(\mathrm{mod}2)$ si et seulement si $x^3+Ax+B$ a une racine dans ${𝔽}_q$, si et seulement si $\gcd (x^q-x,x^3+Ax+B)\ne 1$.

Algorithme

(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)\ne 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 ${𝔽}_q[x,y]/(y^2-x^3-Ax-B,{\psi }_{\ell }).$

(b) Soit $\overline{q}$ le seul entier tel que $q\equiv \overline{q}(\mathrm{mod}\ell )$ et $\mid \overline{q}\mid <\ell /2$.

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

(d) si $x^{q^2}\ne x_{\overline{q}}$ alors

(i) Calculer $(X,Y)$.

(ii) Pour tout $1\le \overline{t}\le (\ell -1)/2$:

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

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

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

(i) calculer $w$ tel que $q\equiv w^2(\mathrm{mod}\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$

(f) 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 $\mathrm{♯}E({𝔽}_q)=q+1-t$.

Complexité

Le calcul le plus coûteux est l'évaluation de $\varphi (P)$ et ${\varphi }^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={𝔽}_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 }^{2}q)$. Par conséquent chaque multiplication dans l'anneau $R$ demande $O({\log }^{4}q)$ multiplications dans ${𝔽}_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)$. Puisqu'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

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,\dots ,{\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 ${\varphi }^2-t\varphi +q=0$ se scinde dans ${𝔽}_{\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. À 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: $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é 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.

Implémentations

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.
• Le logiciel Magma (logiciel) contient une implémentation de SEA pour tout corps fini.
• Mike Scott a mis dans le domaine public une implémentation en C++ 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

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

Références

• 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({𝔽}_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