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.

Inleiding

Laat G een groep zijn, met orde p, en G cyclisch. Laat g $\in$ G voortbrenger zijn van G en h $\in$ G. De discrete logaritme luidt nu als volgt: Bepaal de oplossing van $g^{n}=h$.

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 S₁, S₂, S₃ 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

Zij $G$ een groep van orde $p$, $g$ een voortbrenger en $h\in G$. Bepaal de discrete logaritme $n$, waarvoor $g^{n}=h$.

$G$ wordt verdeeld in drie deelverzamelingen $S_{1},S_{2}$ en $S_{3}$ (geen subgroepen) van ongeveer gelijke omvang.

Vervolgens worden de elementen als volgt gerangschikt:

$x_{0}=1$

en

$x_{i+1}=\left\{{\begin{array}{lcl}h\cdot x_{i}&&x_{i}\in S_{1}\\x_{i}^{2}&{\mbox{als }}&x_{i}\in S_{2}\\g\cdot x_{i}&&x_{i}\in S_{3}\end{array}}\right.$

Bovendien worden de gehele getallen $(a_{i})$ en $(b_{i})$ zo gedefinieerd, dat

$a_{0}=b_{0}=0$

en

$a_{i+1}=\left\{{\begin{array}{lcl}a_{i}&&x_{i}\in S_{1}\\2a_{i}{\bmod {p}}&{\mbox{als }}&x_{i}\in S_{2}\\a_{i}+1{\bmod {p}}&&x_{i}\in S_{3}\end{array}}\right.$

$b_{i+1}=\left\{{\begin{array}{lcl}b_{i}+1{\bmod {p}}&&x_{i}\in S_{1}\\2b_{i}{\bmod {p}}&{\mbox{als }}&x_{i}\in S_{2}\\b_{i}&&x_{i}\in S_{3}\end{array}}\right.$

Dan geldt: $x_{i}=g^{a_{i}+b_{i}n},$ want $a_{i}$ is het aantal factoren $g$, en $b_{i}$ het aantal factoren $h=g^{n}$.

Voor zekere indices $i$ en $j$ zal blijken dat:

$x_{i}=g^{a_{i}+b_{i}n}=x_{j}=g^{a_{j}+b_{j}n}$.

Volgens het algoritme van Floyd voor het opsporen van cyclussen is het voldoende te zoeken naar indices $i$ en $j=2i$.

Dan volgt:

$a_{i}+b_{i}n\equiv a_{j}+b_{j}n{\pmod {p}}$,

waaruit het gevraagde getal $n$ berekend kan worden

Voorbeeld

Het element 5 is een voortbrenger van de subgroep $G$ van $\mathbb {Z} _{1000003}^{*}$ met orde 1.000.002. Met het algoritme wordt de discrete logaritme $n$ bepaald, waarvoor $5^{n}=262682{\pmod {1000003}}$.

Verdeel $G$ in drie deelverzamelingen:

$S_{i}=\{x\in G|x\equiv i\!\!\!{\pmod {3}}\},\quad i=1,2,3$

Dan is

$x_{0}=1$

en

$x_{i+1}={\begin{cases}5^{n}\cdot x_{i}&&x_{i}\equiv 1{\pmod {3}}\\x_{i}^{2}&{\mbox{als }}&x_{i}\equiv 2{\pmod {3}}\\5\cdot x_{i}&&x_{i}\equiv 0{\pmod {3}}\end{cases}}$

Zo ontstaat de rij (alles modulo 1000003):

$x_{1}=5^{n}x_{0}=5^{n}=262682\equiv 2{\pmod {3}}$

$x_{2}=x_{1}^{2}=5^{2n}=262682^{2}=626121\equiv 0{\pmod {3}}$

$x_{3}=5x_{2}=5^{2n+1}=5\times 626121=130596\equiv 0{\pmod {3}}$

$x_{4}=5x_{3}=5^{2n+2}=5\times 130596=652980\equiv 0{\pmod {3}}$

$x_{5}=5x_{4}=5^{2n+3}=5\times 652980=264891\equiv 0{\pmod {3}}$

$x_{6}=5x_{5}=5^{2n+4}=5\times 264891=324452\equiv 2{\pmod {3}}$

$x_{7}=x_{6}^{2}=5^{4n+8}=324452^{2}=784500\equiv 0{\pmod {3}}$

$\ldots$

$x_{1785}=5^{249847n+759123}=555013$

$\ldots$

$x_{3570}=5^{388795n+632781}=555013$

Het blijkt dat $x_{1785}=x_{3570}$, dus

$249847\;n+759123\equiv 388795\;n+632781{\pmod {1000002}}$

of

$138948\;n\equiv 126342{\pmod {1000002}}$

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:

$138948/6\;n\equiv 126342/6{\pmod {1000002/6}}$

dus:

$23158\;n\equiv 21057{\pmod {166667}}$,

zodat:

$n=21057\times 23158^{-1}{\pmod {166667}}$

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

$\operatorname {ggd} (23158,166667)=1$

$1=4133\times 166667-29745\times 23158,$

dus

$1\equiv -29745\times 23158\equiv 136922\times 23158{\pmod {166667}}$

Modulo 166667 is de inverse van 23158 dus 136922, zodat

$n=21057\times 136922{\pmod {166667}}$

Er zijn nu 6 mogelijkheden voor n:

$n=21057\times (136922+k\times 166667){\pmod {166667}},\quad k=0,1,2,3,4,5$,

resulterend in:

$n=21057\times 136922\equiv 160788{\pmod {166667}}$ of

$n=21057\times 303589\equiv 660789{\pmod {166667}}$ of

$n=21057\times 470256\equiv 160788{\pmod {166667}}$ of

$n=21057\times 636923\equiv 660789{\pmod {166667}}$ of

$n=21057\times 803590\equiv 160788{\pmod {166667}}$ of

$n=21057\times 970257\equiv 660789{\pmod {166667}}$

Nu is

$5^{160789}=686596{\pmod {1000003}}$

en

$5^{660789}=262682{\pmod {1000003}}$

Dus $n=660789$ is het gezochte getal.

Zie ook

• Baby-steps giant-steps-algoritme
• Indexcalculusalgoritme
• Pohlig-Hellman-algoritme
• Pollards lambda-algoritme

Referenties

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