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 van een positief geheel getal een factorisatie te maken, ook wel genoemd te ontbinden in factoren. Hiervoor maakt hij gebruik van 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 (at random) een keuze gemaakt is (bijvoorbeeld de keuze voor een elliptische kromme), het algoritme op een deterministische, op een eenduidige wijze wordt uitgevoerd. Dit betekent niet, dat je geen gebruik kunt maken van waarschijnlijkheden. Juist bij goed gekozen krommen kun je spreken over een grote mate van waarschijnlijkheid.

Andere factorisatiealgoritmen[bewerken]

ECM is op twee na de snelste manier om een 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 je binnen de verwachte tijd een factor verkrijgt 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 een zeker getal N te ontbinden is in twee priemfactoren p en q, dus N = p . q .

Pollards methode werkt dan eigenlijk alleen indien p-1 of q-1 B-smooth is. (Een getal heet B-smooth indien elke priemfactor van dat getal kleiner is dan B.) Als dat niet het geval is, 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, heb je daarmee veel meer 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 getal n werkt als volgt:

  1. Kies een toevallige elliptische kromme over Z/nZ, 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 = Kleinste gemene veelvoud = kgv (1, 2, 3, …, B). 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 = ggd ((x_1-x_2) , n)
  8. Als g\not\in \{1,n\}, dan is g een niet-triviale factor van n.

Anders kiezen we een ander punt op de kromme of we kiezen een andere elliptische kromme.

Een voorbeeld[bewerken]

In dit voorbeeld willen we een factor vinden van 5959 met behulp van Lenstra's ECM. We kiezen dus n= 5959

  1. We kiezen de elliptische kromme
    y^2=x^3+1201x+1 over Z/5959Z
  2. Op deze kromme kiezen we het punt P=(0,1)
  3. We kiezen B = 20
  4. k= kgv (1 , 2 , 3 , … , 20) = 232792560 = 1101111000000010000111110000 (binair)
  5. Bereken 2^i.P = 2^i.(0,1) met
    i\in K = \{4 , 5 , 6 , 7 , 8 , 13 , 21 , 22 , 23 , 24 , 26 , 27 \}
    Natuurlijk heb je hier een computerprogramma voor nodig. Dan is
    kP = \sum_{i\in K}2^iP
  6. Met de computerprogramma’s is ook van elk tweetal punten
    \lambda=\frac{y_1-y_2}{x_1-x_2} te berekenen
  7. Bepaal voor elk tweetal punten g = ggd ((x_1-x_2) , n)
  8. Het blijkt dat uit geen enkele g een niet-triviale oplossing komt, dus zo komen we niet tot een factorisatie van 5959.

Als we bovenstaand algoritme nogmaals doorwandelen met de elliptische kromme

y^2=x^3+389x+1 over Z/5959Z

en het punt P=(0,1) op deze kromme, dan komen we op een gegeven moment bij de punten Q=(2051,5273) en R=(637,1292). Als we deze twee punten optellen op de wijze zoals gedefinieerd is voor elliptische krommen, dan vinden we

\lambda=\frac{y_1-y_2}{x_1-x_2} = \frac{5273-1292}{2051-637} = \frac{3981}{1414}.

Dan is

g = ggd (1414,5959)=101

en zo vinden we de niet-triviale factor 101 van 5959.

Bronnen, noten en/of referenties