Voir la source de Factorisation de Lenstra par les courbes elliptiques

{{Ébauche|informatique|informatique théorique|mathématiques}}
{{À sourcer|date=septembre 2020}}
{{Voir homonymes|ECM}}

La '''factorisation de [[Hendrik Lenstra|Lenstra]] par les courbes elliptiques''' (en [[anglais]], ''{{lang|en|elliptic-curve factorization method}}'' ou ''ECM'') est un [[algorithme probabiliste]] rapide pour la [[décomposition en produit de facteurs premiers]] qui emploie les [[courbe elliptique|courbes elliptiques]]. 

Cette méthode fut le meilleur [[Algorithmique|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 [[diviseur]]s 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 <math>p</math> plutôt que de la taille du nombre <math>n</math> à factoriser.

== Description ==

C'est une amélioration de la traditionnelle [[algorithme p-1 de Pollard|méthode de factorisation ''p''−1 de Pollard]]. Dans cette méthode, il était supposé que le nombre donné <math>n</math> possède un facteur [[nombre premier|premier]] <math>p</math> tel que <math>p-1</math> possède seulement des « petits » facteurs premiers (les nombres dont les facteurs premiers sont tous « petits » sont dits [[Nombre_lisse|friables]]). Alors, par le [[petit théorème de Fermat]], <math>a^e=1\mod p</math> dès que <math>p-1</math> divise <math>e</math> et <math>p</math> ne divise pas <math>a</math>. En prenant pour <math>e</math> un produit de petits nombres premiers élevés aux petites puissances, et <math>a</math> comme un résidu aléatoire [[Modulo (opération)|modulo]] <math>n</math>, nous pouvons espérer factoriser <math>n</math> en calculant le [[PGCD]] de <math>n</math> et <math>a^e-1</math>, {{pas clair|comme les autres diviseurs ''q'' de ''n'' ne semblent pas avoir la propriété ''q''-1 divise ''e'' - les valeurs friables sont rares}}. Néanmoins, l'on ne pourra pas factoriser <math>n</math> si <math>n</math> n'a pas un facteur premier <math>p</math> avec <math>p-1</math> friable.

La factorisation de Lenstra contourne cet obstacle en considérant le [[groupe (mathématiques)|groupe]] d'une [[courbe elliptique]] aléatoire sur le [[corps fini]] '''F'''<sub>''p''</sub>, plutôt que sur le groupe multiplicatif de '''F'''<sub>''p''</sub> qui a toujours un ordre ''p''-1. L'ordre du groupe d'une courbe elliptique sur '''F'''<sub>''p''</sub> varie entre <math>p+1-2\sqrt p</math> et <math>p+1+2\sqrt p</math> (un théorème de [[Helmut Hasse]]) aléatoirement, et {{pas clair|doit être probablement}} 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]] {{pas clair|et en trouvant un résidu non-inversible équivalent à la factorisation de ''n''}}.
* 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. {{pas clair|Il peut donner un nombre premier en une fois, et est ainsi efficace.}}
* Avec un peu de chance, ''eA'' est l'élément nul du groupe de la courbe elliptique dans '''F'''<sub>''p''</sub>, mais pas dans '''F'''<sub>''q''</sub> 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 '''F'''<sub>''p''</sub>.
* Si cela ne marche pas, il suffit de recommencer avec une autre courbe ou un autre point de départ.

La [[Analyse de la complexité des algorithmes|complexité de l'algorithme]] dépend de la taille du facteur à trouver ; elle peut être exprimée par [[Comparaison asymptotique|O]]([[fonction exponentielle|e]]<sup>({{racine|2}} + o(1)) {{racine|[[logarithme naturel|ln]] ''p'' ln ln ''p''}}</sup>) où ''p'' est le plus petit facteur de ''n''.

== Bibliographie ==
* {{Ouvrage| langue=en| auteur1=[[Samuel Wagstaff|Samuel S. Wagstaff, Jr.]]| titre=The Joy of Factoring| éditeur=[[American Mathematical Society]]| collection=Student Mathematical Library| lieu=Providence, RI| numéro dans collection=68| année=2013| pages totales=293| isbn=978-1-4704-1048-3| présentation en ligne=https://bookstore.ams.org/stml-68| numéro chapitre=7| titre chapitre=Elliptic curves}}

== Notes et références ==
{{Références}}
{{Traduction/Référence|en|Lenstra elliptic curve factorization|8238252}}

{{Portail|Mathématiques}}

[[Catégorie:Algorithme de factorisation des entiers]]