Pollards rho-algoritme

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.

InleidingBewerken

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.)

AlgoritmeBewerken

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

VoorbeeldBewerken

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):

 
 
 
 
 
 
 
 
 
 
 

 

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 ookBewerken

ReferentiesBewerken

  • (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.