Factorisation de Lenstra par les courbes elliptiques
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/02/Circle-icons-computer.svg/35px-Circle-icons-computer.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/44px-Max-cut.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Racine_carr%C3%A9e_bleue.svg/35px-Racine_carr%C3%A9e_bleue.svg.png)
Cet article est une ébauche concernant l’informatique, l’informatique théorique et les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
![Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Info_Simple.svg/12px-Info_Simple.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a1/2017-fr.wp-orange-source.svg/45px-2017-fr.wp-orange-source.svg.png)
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
![Page d’aide sur l’homonymie](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/20px-Logo_disambig.svg.png)
Pour les articles homonymes, voir ECM.
La factorisation de Lenstra par les courbes elliptiques (en anglais, elliptic-curve factorization method ou ECM) est un algorithme probabiliste rapide pour la décomposition en produit de facteurs premiers qui emploie les courbes elliptiques.
Cette méthode fut le meilleur algorithme pour la décomposition en produit de facteurs premiers jusqu'au développement du crible général de corps de nombres (GNFS). Il est encore le meilleur pour l'extraction des diviseurs dont la taille ne dépasse pas 20 chiffres (ce qui inclut les entiers sur 64 bits), car son temps d'exécution dépend de la taille d'un facteur plutôt que de la taille du nombre à factoriser.
Description
C'est une amélioration de la traditionnelle méthode de factorisation p−1 de Pollard. Dans cette méthode, il était supposé que le nombre donné possède un facteur premier tel que possède seulement des « petits » facteurs premiers (les nombres dont les facteurs premiers sont tous « petits » sont dits friables). Alors, par le petit théorème de Fermat, dès que divise et ne divise pas . En prenant pour un produit de petits nombres premiers élevés aux petites puissances, et comme un résidu aléatoire modulo , nous pouvons espérer factoriser en calculant le PGCD de et , comme les autres diviseurs q de n ne semblent pas avoir la propriété q-1 divise e - les valeurs friables sont rares[pas clair]. Néanmoins, l'on ne pourra pas factoriser si n'a pas un facteur premier avec friable.
La factorisation de Lenstra contourne cet obstacle en considérant le groupe d'une courbe elliptique aléatoire sur le corps fini Fp, plutôt que sur le groupe multiplicatif de Fp qui a toujours un ordre p-1. L'ordre du groupe d'une courbe elliptique sur Fp varie entre et (un théorème de Helmut Hasse) aléatoirement, et doit être probablement[pas clair] friable pour certaines courbes elliptiques.
L'algorithme de factorisation de Lenstra permettant de trouver un facteur d'un nombre donné n fonctionne de la manière suivante.
- Prendre une courbe elliptique aléatoire sur Z avec un point A sur elle. Alors, nous considérons la loi de groupe sur cette courbe modulo n - ceci est possible car la plupart des résidus modulo n ont des inverses, qui peuvent être trouvés en utilisant l'algorithme d'Euclide et en trouvant un résidu non-inversible équivalent à la factorisation de n[pas clair].
- Calculer eA dans ce groupe, où e est le produit de petits nombres premiers élevés aux petites puissances, comme dans la méthode p−1 de Pollard. Il peut donner un nombre premier en une fois, et est ainsi efficace.[pas clair]
- Avec un peu de chance, eA est l'élément nul du groupe de la courbe elliptique dans Fp, mais pas dans Fq pour un autre diviseur premier q de n (comme dans la méthode p−1 de Pollard, il est très improbable que les deux groupes aient un ordre qui soit un diviseur de e). Alors nous pouvons trouver un facteur de n en calculant le PGCD de la première coordonnée de A et n, car cette coordonnée sera nulle dans Fp.
- Si cela ne marche pas, il suffit de recommencer avec une autre courbe ou un autre point de départ.
La complexité de l'algorithme dépend de la taille du facteur à trouver ; elle peut être exprimée par O(e(√2 + o(1)) √ln p ln ln p) où p est le plus petit facteur de n.
Bibliographie
- (en) Samuel S. Wagstaff, Jr., The Joy of Factoring, Providence, RI, American Mathematical Society, coll. « Student Mathematical Library » (no 68), , 293 p. (ISBN 978-1-4704-1048-3, présentation en ligne), chap. 7 (« Elliptic curves »)
Notes et références
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Lenstra elliptic curve factorization » (voir la liste des auteurs).
Portail des mathématiques