Pollards rho-algoritme

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

Pollards rho-algoritme is een algoritme dat door John Pollard in 1978 beschreven werd om de discrete logaritme zoals dat is gedefinieerd in een cyclische groep te berekenen. Het grote voordeel ten opzichte van het Baby-steps giant-steps-algoritme is dat voor deze methode geen opslagruimte nodig is.

Inleiding[bewerken]

Laat G een groep zijn, met orde p, en G cyclisch. Laat g G voortbrenger zijn van G en h G. De discrete logaritme luidt nu als volgt: Bepaal de oplossing van .

Pollards rho-algoritme definieert eerst een pseudowillekeurige reeks (opeenvolging) van elementen van een groep en kijkt dan naar een cyclus (kringloop) die in deze reeks voorkomt.

Deze groep wordt verdeeld in drie deelverzamelingen S1, S2, S3 van ongeveer gelijke grootte, door middel van een eenvoudig te testen eigenschap.

Vervolgens wordt er een functie gedefinieerd die de groep afbeeldt op zichzelf waardoor de elementen op een andere manier worden gerangschikt. Verder wordt f(x) zo gekozen dat elk opeenvolgend element een functie is van alleen het voorgaande element. Eigenlijk worden twee reeksen elementen gemaakt waarbij de tweede reeks twee keer zo snel de groepselementen doorloopt als de eerste reeks. We zoeken nu totdat we twee dezelfde elementen hebben gevonden. Als we een element vinden dat voor de tweede keer voorkomt, is elk daaropvolgend element een herhaling van elementen eerder in de reeks.

De verjaardagenparadox zegt nu dat we zo’n cyclus zullen vinden nadat we slechts O(√p) elementen van de reeks hebben berekend. (In het algemeen geldt dat als er volkomen willekeurig elementen worden geselecteerd uit een verzameling, met grootte n dan hoeft men maar O(√p) elementen van deze verzameling te selecteren om een kans van ½ te hebben om hetzelfde element twee keer te trekken.)

Algoritme[bewerken]

Zij een groep van orde , een voortbrenger en . Bepaal de discrete logaritme , waarvoor .

wordt verdeeld in drie deelverzamelingen en (geen subgroepen) van ongeveer gelijke omvang.

Vervolgens worden de elementen als volgt gerangschikt:

en

Bovendien worden de gehele getallen en zo gedefinieerd, dat

en

Dan geldt: want is het aantal factoren , en het aantal factoren .

Voor zekere indices en zal blijken dat:

.

Volgens het algoritme van Floyd voor het opsporen van cyclussen is het voldoende te zoeken naar indices en .

Dan volgt:

,

waaruit het gevraagde getal berekend kan worden

Voorbeeld[bewerken]

Het element 5 is een voortbrenger van de subgroep van met orde 1.000.002. Met het algoritme wordt de discrete logaritme bepaald, waarvoor .

Verdeel in drie deelverzamelingen:

Dan is

en

Zo ontstaat de rij (alles modulo 1000003):

Pollard rho cycle.jpg

Het blijkt dat , dus

of

Omdat 138948 en 1000002 niet relatief priem zijn (ggd(138948,1000002) = 6), heeft 138948 geen inverse en kan de congruentievergelijking niet direct opgelost worden. Een vergelijkbare vergelijking is:

dus:

,

zodat:

De inverse van 23158 (mod 166667) kan berekend worden met het uitgebreide algoritme van Euclides:

dus

Modulo 166667 is de inverse van 23158 dus 136922, zodat

Er zijn nu 6 mogelijkheden voor n:

,

resulterend in:

of
of
of
of
of

Nu is

en

Dus is het gezochte getal.

Zie ook[bewerken]

Referenties[bewerken]

  • (en) Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of applied cryptography, 2001.
  • (en) D.J. Bernstein, Generic attacks and index calculus , University of Illinois, Chicago.
  • (en) Neal Koblitz, A Course in Elementary Number Theory and Cryptography, Springer.
  • (en) J. M. Pollard, Monte Carlo methods for index computation mod p, Mathematics of Computation, Volume 32, Issue 143 (jul.1978), 918-924.
  • (en) D. Hankerson and Alfred J. Menezes, The Discrete Logarithm Problem, Auburn University and University of waterloo, Jun. 17, 2004.