Algoritme van Lenstra

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Het algoritme van Lenstra is een algoritme dat is ontwikkeld door Hendrik Lenstra, om een positief geheel getal te factoriseren, d.w.z. te ontbinden in factoren. Hiertoe gebruikt het algoritme een elliptische kromme. Daarom duidt men dit algoritme aan met de letters ECM (Elliptic Curve Method). 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[bewerken]

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 zijn zogenaamde ‘probabilistische’ algoritmen, waarbij meer gebruikgemaakt wordt van waarschijnlijkheid. Hierbij is echt 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, dan 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 te vinden van een getal tot ongeveer 25 cijfers.(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. Op 24 augustus 2006 heeft B. Dodson 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.

Motivatie voor ECM[bewerken]

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 indien of zogenaamd -smooth is, d.w.z. dat elke 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[bewerken]

Het algoritme van Lenstra’s ECM om een factor te vinden van een zeker natuurlijk getal werkt als volgt:

  1. Kies een willekeurige elliptische kromme over , gegeven door de vergelijking
    .
  2. Kies een niet-triviaal punt op deze kromme.
  3. Kies een getal , niet te groot en niet te klein. Dit getal wordt ingezet als -smooth getal.
  4. Vind (kleinste gemene veelvoud). Het is voor de verdere berekening vaak handig en dus gebruikelijk om binair te schrijven.
  5. Bepaal door gebruik te maken van de optellingen en andere berekeningen zoals die zijn gedefinieerd voor elliptische krommen.
  6. Bepaal voor elke optelling
  7. Bepaal (grootste_gemene_deler).
  8. Als , is een niet-triviale factor van . Is dit niet het geval dan moet een ander punt ofneenandere elliptische kromme gekozen worden.

Voorbeeld[bewerken]

Van het getal wordt met Lenstra's ECM een factor gezocht.

  1. Kies als elliptische kromme
    over
  2. Kies op deze kromme het punt .
  3. Neem .
  4. Dan is (binair)
  5. Bereken voor
  6. Dan is
  7. Bereken van elk tweetal punten
  8. Bepaal voor elk tweetal punten
  9. 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.