Algoritme van Lenstra
Het algoritme van Lenstra of de Elliptic Curve Method ECM is een algoritme dat is ontwikkeld door Hendrik Lenstra, om een positief geheel getal te factoriseren, te ontbinden in factoren. Hiertoe gebruikt het algoritme een elliptische kromme. De ECM is een zogenaamd ’deterministisch’ algoritme. Dit houdt in dat, als eenmaal willekeurig een keuze gemaakt is, bijvoorbeeld de keuze voor een elliptische kromme, het algoritme op een deterministische, dus eenduidige wijze wordt uitgevoerd.

Andere factorisatiealgoritmen 
ECM is op twee na de snelste manier om de factorisatie van een getal te vinden. De snelste manier is de getallenlichamenzeef, gevolgd door de kwadratische zeef. Deze methoden worden ‘probabilistische’ algoritmen genoemd. Hierbij is het echter niet gegarandeerd dat binnen de verwachte tijd een factor verkregen wordt die niet triviaal is. ECM wordt beschouwd als een factorisatie met een hoge verwachtingswaarde, die het meest geschikt is voor het vinden van een betrekkelijk kleine factor. Vaak wordt ECM gebruikt om betrekkelijk kleine factoren te verwijderen van een erg groot getal met veel factoren. Als het overblijvende getal nog steeds een samengesteld getal is, heeft het alleen maar grote factoren en zullen andere technieken gebruikt moeten worden, of het is bijna onmogelijk om factoren te vinden. Op dit moment is het nog steeds het beste algoritme om delers van een getal tot ongeveer 25 cijfers te vinden, van ongeveer 80 bit. Hierbij wordt de tijd voor het vinden van een factor meer bepaald door de grootte van de kleinste factor  dan door de grootte van het te factoriseren getal  zelf. B. Dodson heeft op 24 augustus 2006 een getal van 67 cijfers ontbonden in factoren door gebruik te maken van ECM. Weliswaar is de kans op het vinden van een factor groter naarmate men meer krommen gebruikt, maar het aantal ingezette krommen loopt (helaas) niet lineair met het aantal cijfers van het te ontbinden getal.

Toelichting 
In feite is de ECM een uitbreiding van Pollards p–1-methode.

Stel dat het te ontbinden getal  het product is van twee priemfactoren  en , dus .

Pollards methode werkt dan eigenlijk alleen als  of  zogenaamd -smooth is, of hetzelfde als iedere priemfactor kleiner is dan . Is dat niet het geval, dan is het ondoenlijk om met de manier van Pollard een ontbinding te vinden. Omdat de ECM werkt met groepen van punten op een elliptische kromme, is er een grotere kans op het gewenste resultaat.

Het algoritme van Lenstra voor factorisatie met de ECM 
Het algoritme van Lenstra’s ECM om een factor te vinden van een zeker natuurlijk getal  werkt als volgt:
 Kies een willekeurige elliptische kromme over , gegeven door de vergelijking
.
 Kies een niet-triviaal punt  op deze kromme.
 Kies een getal , niet te groot en niet te klein. Dit getal wordt ingezet als -smooth getal.
 Vind .  staat voor kleinste gemene veelvoud. Het is voor de verdere berekening vaak handig en dus gebruikelijk om  binair te schrijven.
 Bepaal  door gebruik te maken van de optellingen en andere berekeningen zoals die zijn gedefinieerd voor elliptische krommen.
 Bepaal voor elke optelling 
 Bepaal .  staat voor grootste gemene deler.
 Als , is  een niet-triviale factor van . Is dit niet het geval dan moet een ander punt  of een andere elliptische kromme gekozen worden.

Voorbeeld 
Van het getal  wordt met Lenstra's ECM een factor gezocht. 
 Kies als elliptische kromme
 over 
 Kies op deze kromme het punt .
 Neem .
 Dan is  (binair)
 Bereken  voor

 Dan is 
 Bereken van elk tweetal punten

 Bepaal voor elk tweetal punten 
 Het blijkt dat uit geen enkele  een niet-triviale oplossing komt, en dus geen factor van 5959 gevonden wordt.

Met een andere elliptische kromme
 over 
en het punt  op deze kromme, komt men bij de punten  en . Optellen op de wijze zoals gedefinieerd is voor elliptische krommen, levert
.
Dan is
,
waaruit de niet-triviale factor 101 van 5959 volgt.

Algoritme
Priemgetaltest