Algorithme de Schoof

Cet article est une ébauche concernant la cryptologie. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

L'algorithme de Schoof est un algorithme décrit pour la première fois en 1985 par René Schoof (de), permettant de déterminer le nombre de points sur une courbe elliptique, particulièrement pour la cryptographie sur les courbes elliptiques.

Principe

Le théorème de Hasse sur les courbes elliptiques fournit l'approximation :

$| E(\mathbb{F}_q) - (q+1) | \leq 2 \sqrt{q}$,

alors pour trouver le nombre exact de points, il est suffisant de trouver ce nombre modulo $R > 4 \sqrt{q}$.

L'algorithme de Schoof calcule

$q+1 - |E(\mathbb{F}_q)| \pmod{r_i}$

pour plusieurs petits nombres premiers $r_i$, où $\prod r_i = R$. Le résultat final est obtenu par combinaison via le théorème des restes chinois.

Analyse

La complexité de l'algorithme original est $(\log q)^8$ et a été améliorée à $O((\log q)^6)$. C'est une complexité pratique pour un ordinateur personnel, avec $q < 256$.

L'algorithme a été étendu par Noam Elkies et A. O. L. Atkin (en) pour donner l'algorithme de Schoof-Elkies-Atkin (en), qui a une meilleure complexité asymptotique, de $O((\log q)^5)$.

Références

• (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)
• (en) R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Mathematics of Computation, Volume 44, 1985.