Algorithme de Schoof

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

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[modifier | modifier le code]

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[modifier | modifier le code]

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