Factorisation de Lenstra par les courbes elliptiques
# Factorisation de Lenstra par les courbes elliptiques

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 p plutôt que de la taille du nombre n à factoriser.

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é n possède un facteur premier p tel que p-1 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, ae=1 mod p dès que p-1 divise e et p ne divise pas a. En prenant pour e un produit de petits nombres premiers élevés aux petites puissances, et a comme un résidu aléatoire modulo n, nous pouvons espérer factoriser n en calculant le PGCD de n et ae-1, 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 n si n n'a pas un facteur premier p avec p-1 friable.

La factorisation de Lenstra contourne cet obstacle en considérant le groupe d'une courbe elliptique aléatoire sur le corps fini $F_p,$ plutôt que sur le groupe multiplicatif de $F_p$ qui a toujours un ordre p-1. L'ordre du groupe d'une courbe elliptique sur $F_p$ varie entre $p+1-2{\sqrt {p}}$ et $p+1+2{\sqrt {p}}$ (un théorème de Helmut Hasse) aléatoirement, et 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.

La complexité de l'algorithme dépend de la taille du facteur à trouver ; elle peut être exprimée par O(e) où p est le plus petit facteur de n.

