Algorithme De Schoof

Algorithme de Schoof

L'algorithme de Schoof est un algorithme décrit pour la première fois en 1985 par R. Schoof, 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 \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.

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).

Référence

  • R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Mathematics of Computation, Volume 44, 1985.
  • Portail des mathématiques Portail des mathématiques
  • Portail de la cryptologie Portail de la cryptologie
Ce document provient de « Algorithme de Schoof ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme De Schoof de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Algorithme de schoof — L algorithme de Schoof est un algorithme décrit pour la première fois en 1985 par R. Schoof, permettant de déterminer le nombre de points sur une courbe elliptique, particulièrement pour la cryptographie sur les courbes elliptiques. Principe Le… …   Wikipédia en Français

  • Algorithme de Schoof — L algorithme de Schoof est un algorithme décrit pour la première fois en 1985 par René Schoof, permettant de déterminer le nombre de points sur une courbe elliptique, particulièrement pour la cryptographie sur les courbes elliptiques. Principe Le …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Théorème de Hasse sur les courbes elliptiques — Théorème de Hasse En mathématiques, le théorème de Hasse sur les courbes elliptiques limite le nombre de points d une courbe elliptique sur un corps fini, au dessus et en dessous. Si N est le nombre de points d une courbe elliptique E sur un… …   Wikipédia en Français

  • Théorème de hasse — En mathématiques, le théorème de Hasse sur les courbes elliptiques limite le nombre de points d une courbe elliptique sur un corps fini, au dessus et en dessous. Si N est le nombre de points d une courbe elliptique E sur un corps fini à q… …   Wikipédia en Français

  • Théorème de Hasse — En mathématiques, le théorème de Hasse sur les courbes elliptiques limite le nombre de points d une courbe elliptique sur un corps fini, au dessus et en dessous. Si N est le nombre de points d une courbe elliptique E sur un corps fini à q… …   Wikipédia en Français

  • Noam Elkies — Noam David Elkies Noam Elkies en 2007 à Oberwolfach Naissance 25 août 1966 New York (États Unis) Nationalité Américaine Isr …   Wikipédia en Français

  • Cryptographie Sur Les Courbes Elliptiques — En cryptographie, les courbes elliptiques, des objets mathématiques, peuvent être utilisées pour des opérations asymétriques comme des échanges de clés sur un canal non sécurisé ou un chiffrement asymétrique, on parle alors de cryptographie sur… …   Wikipédia en Français

  • Cryptographie par courbe elliptique — Cryptographie sur les courbes elliptiques En cryptographie, les courbes elliptiques, des objets mathématiques, peuvent être utilisées pour des opérations asymétriques comme des échanges de clés sur un canal non sécurisé ou un chiffrement… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”