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 $p$ dan door de grootte van het te factoriseren getal $n$ 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 $N$ het product is van twee priemfactoren $p$ en $q$, dus $N=p\cdot q$.

Pollards methode werkt dan eigenlijk alleen als $p-1$ of $q-1$ zogenaamd $B$-smooth is, of hetzelfde als iedere priemfactor kleiner is dan $B$. 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 $n$ werkt als volgt:

1. Kies een willekeurige elliptische kromme over $\mathbb {Z} /n\mathbb {Z}$, gegeven door de vergelijking

   $y^{2}=x^{3}+ax+b$.

2. Kies een niet-triviaal punt $P$ op deze kromme.
3. Kies een getal $B$, niet te groot en niet te klein. Dit getal wordt ingezet als $B$-smooth getal.
4. Vind $k=\mathrm {kgv} (1,2,\ldots ,B)$. $\mathrm {kgv}$ staat voor kleinste gemene veelvoud. Het is voor de verdere berekening vaak handig en dus gebruikelijk om $k$ binair te schrijven.
5. Bepaal $kP$ door gebruik te maken van de optellingen en andere berekeningen zoals die zijn gedefinieerd voor elliptische krommen.
6. Bepaal voor elke optelling $\lambda ={\frac {y_{1}-y_{2}}{x_{1}-x_{2}}}$
7. Bepaal $g=\mathrm {ggd} ((x_{1}-x_{2}),n)$. $\mathrm {ggd}$ staat voor grootste gemene deler.
8. Als $g\not \in \{1,n\}$, is $g$ een niet-triviale factor van $n$. Is dit niet het geval dan moet een ander punt $P$ of een andere elliptische kromme gekozen worden.

Voorbeeld

Van het getal $n=5959$ wordt met Lenstra's ECM een factor gezocht.

1. Kies als elliptische kromme

   $y^{2}=x^{3}+1201x+1$ over $\mathbb {Z} /5959\,\mathbb {Z}$

2. Kies op deze kromme het punt $P=(0,1)$.
3. Neem $B=20$.
4. Dan is $k=\mathrm {kgv} (1,2,\ldots ,20)=232792560=1101111000000010000111110000$ (binair)
5. Bereken $2^{i}\cdot P=2^{i}\cdot (0,1)$ voor

   $i\in K=\{4,5,6,7,8,13,21,22,23,24,26,27\}$

6. Dan is $kP=\sum _{i\in K}2^{i}P$
7. Bereken van elk tweetal punten

   $\lambda ={\frac {y_{1}-y_{2}}{x_{1}-x_{2}}}$

8. Bepaal voor elk tweetal punten $g=\mathrm {ggd} ((x_{1}-x_{2}),n)$
9. Het blijkt dat uit geen enkele $g$ een niet-triviale oplossing komt, en dus geen factor van 5959 gevonden wordt.

Met een andere elliptische kromme

$y^{2}=x^{3}+389x+1$ over $\mathbb {Z} /5959\,\mathbb {Z}$

en het punt $P=(0,1)$ op deze kromme, komt men bij de punten $Q=(2051,5273)$ en $R=(637,1292)$. Optellen op de wijze zoals gedefinieerd is voor elliptische krommen, levert

$\lambda ={\frac {y_{1}-y_{2}}{x_{1}-x_{2}}}={\frac {5273-1292}{2051-637}}={\frac {3981}{1414}}$.

Dan is

$g=\mathrm {ggd} (1414,5959)=101$,

waaruit de niet-triviale factor 101 van 5959 volgt.