Algorithme de Schoof

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant la cryptologie.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

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

[modifier] Principe

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

|E(\mathbb{F}_q)| = q + 1 \pm 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 ri, où \prod r_i = R. Le résultat final est obtenu par combinaison via le théorème des restes chinois.

[modifier] Analyse

La complexité de l'algorithme original est (logq)8 et a été améliorée à O((logq)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 pour donner l'algorithme de Schoof-Elkies-Atkin, qui a une meilleure complexité asymptotique, de O((logq)5).

[modifier] Référence

  • R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Mathematics of Computation, Volume 44, 1985.
Autres langues