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.
Laat G een groep zijn, met orde p, en G cyclisch . Laat g
∈
{\displaystyle \in }
voortbrenger zijn van G en h
∈
{\displaystyle \in }
g
n
=
h
{\displaystyle 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 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.)
Zij
G
{\displaystyle G}
groep van orde
p
{\displaystyle p}
g
{\displaystyle g}
h
∈
G
{\displaystyle h\in G}
discrete logaritme
n
{\displaystyle n}
g
n
=
h
{\displaystyle g^{n}=h}
G
{\displaystyle G}
deelverzamelingen
S
1
,
S
2
{\displaystyle S_{1},S_{2}}
S
3
{\displaystyle S_{3}}
subgroepen ) van ongeveer gelijke omvang.
Vervolgens worden de elementen als volgt gerangschikt:
x
0
=
1
{\displaystyle x_{0}=1}
en
x
i
+
1
=
{
h
⋅
x
i
x
i
∈
S
1
x
i
2
als
x
i
∈
S
2
g
⋅
x
i
x
i
∈
S
3
{\displaystyle 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
)
{\displaystyle (a_{i})}
(
b
i
)
{\displaystyle (b_{i})}
a
0
=
b
0
=
0
{\displaystyle a_{0}=b_{0}=0}
en
a
i
+
1
=
{
a
i
x
i
∈
S
1
2
a
i
mod
p
als
x
i
∈
S
2
a
i
+
1
mod
p
x
i
∈
S
3
{\displaystyle 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
=
{
b
i
+
1
mod
p
x
i
∈
S
1
2
b
i
mod
p
als
x
i
∈
S
2
b
i
x
i
∈
S
3
{\displaystyle 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
,
{\displaystyle x_{i}=g^{a_{i}+b_{i}n},}
a
i
{\displaystyle a_{i}}
g
{\displaystyle g}
b
i
{\displaystyle b_{i}}
h
=
g
n
{\displaystyle h=g^{n}}
Voor zekere indices
i
{\displaystyle i}
j
{\displaystyle j}
x
i
=
g
a
i
+
b
i
n
=
x
j
=
g
a
j
+
b
j
n
{\displaystyle 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
{\displaystyle i}
j
=
2
i
{\displaystyle j=2i}
Dan volgt:
a
i
+
b
i
n
≡
a
j
+
b
j
n
(
mod
p
)
{\displaystyle a_{i}+b_{i}n\equiv a_{j}+b_{j}n{\pmod {p}}}
waaruit het gevraagde getal
n
{\displaystyle n}
Het element 5 is een voortbrenger van de subgroep
G
{\displaystyle G}
Z
1000003
∗
{\displaystyle \mathbb {Z} _{1000003}^{*}}
n
{\displaystyle n}
5
n
=
262682
(
mod
1000003
)
{\displaystyle 5^{n}=262682{\pmod {1000003}}}
Verdeel
G
{\displaystyle G}
S
i
=
{
x
∈
G
|
x
≡
i
(
mod
3
)
}
,
i
=
1
,
2
,
3
{\displaystyle S_{i}=\{x\in G|x\equiv i\!\!\!{\pmod {3}}\},\quad i=1,2,3}
Dan is
x
0
=
1
{\displaystyle x_{0}=1}
en
x
i
+
1
=
{
5
n
⋅
x
i
x
i
≡
1
(
mod
3
)
x
i
2
als
x
i
≡
2
(
mod
3
)
5
⋅
x
i
x
i
≡
0
(
mod
3
)
{\displaystyle 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
≡
2
(
mod
3
)
{\displaystyle x_{1}=5^{n}x_{0}=5^{n}=262682\equiv 2{\pmod {3}}}
x
2
=
x
1
2
=
5
2
n
=
262682
2
=
626121
≡
0
(
mod
3
)
{\displaystyle x_{2}=x_{1}^{2}=5^{2n}=262682^{2}=626121\equiv 0{\pmod {3}}}
x
3
=
5
x
2
=
5
2
n
+
1
=
5
×
626121
=
130596
≡
0
(
mod
3
)
{\displaystyle x_{3}=5x_{2}=5^{2n+1}=5\times 626121=130596\equiv 0{\pmod {3}}}
x
4
=
5
x
3
=
5
2
n
+
2
=
5
×
130596
=
652980
≡
0
(
mod
3
)
{\displaystyle x_{4}=5x_{3}=5^{2n+2}=5\times 130596=652980\equiv 0{\pmod {3}}}
x
5
=
5
x
4
=
5
2
n
+
3
=
5
×
652980
=
264891
≡
0
(
mod
3
)
{\displaystyle x_{5}=5x_{4}=5^{2n+3}=5\times 652980=264891\equiv 0{\pmod {3}}}
x
6
=
5
x
5
=
5
2
n
+
4
=
5
×
264891
=
324452
≡
2
(
mod
3
)
{\displaystyle x_{6}=5x_{5}=5^{2n+4}=5\times 264891=324452\equiv 2{\pmod {3}}}
x
7
=
x
6
2
=
5
4
n
+
8
=
324452
2
=
784500
≡
0
(
mod
3
)
{\displaystyle x_{7}=x_{6}^{2}=5^{4n+8}=324452^{2}=784500\equiv 0{\pmod {3}}}
…
{\displaystyle \ldots }
x
1785
=
5
249847
n
+
759123
=
555013
{\displaystyle x_{1785}=5^{249847n+759123}=555013}
…
{\displaystyle \ldots }
x
3570
=
5
388795
n
+
632781
=
555013
{\displaystyle x_{3570}=5^{388795n+632781}=555013}
Het blijkt dat
x
1785
=
x
3570
{\displaystyle x_{1785}=x_{3570}}
249847
n
+
759123
≡
388795
n
+
632781
(
mod
1000002
)
{\displaystyle 249847\;n+759123\equiv 388795\;n+632781{\pmod {1000002}}}
of
138948
n
≡
126342
(
mod
1000002
)
{\displaystyle 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
≡
126342
/
6
(
mod
1000002
/
6
)
{\displaystyle 138948/6\;n\equiv 126342/6{\pmod {1000002/6}}}
dus:
23158
n
≡
21057
(
mod
166667
)
{\displaystyle 23158\;n\equiv 21057{\pmod {166667}}}
zodat:
n
=
21057
×
23158
−
1
(
mod
166667
)
{\displaystyle n=21057\times 23158^{-1}{\pmod {166667}}}
De inverse van 23158 (mod 166667) kan berekend worden met het uitgebreide algoritme van Euclides :
ggd
(
23158
,
166667
)
=
1
{\displaystyle \operatorname {ggd} (23158,166667)=1}
1
=
4133
×
166667
−
29745
×
23158
,
{\displaystyle 1=4133\times 166667-29745\times 23158,}
dus
1
≡
−
29745
×
23158
≡
136922
×
23158
(
mod
166667
)
{\displaystyle 1\equiv -29745\times 23158\equiv 136922\times 23158{\pmod {166667}}}
Modulo 166667 is de inverse van 23158 dus 136922, zodat
n
=
21057
×
136922
(
mod
166667
)
{\displaystyle n=21057\times 136922{\pmod {166667}}}
Er zijn nu 6 mogelijkheden voor n:
n
=
21057
×
(
136922
+
k
×
166667
)
(
mod
166667
)
,
k
=
0
,
1
,
2
,
3
,
4
,
5
{\displaystyle n=21057\times (136922+k\times 166667){\pmod {166667}},\quad k=0,1,2,3,4,5}
resulterend in:
n
=
21057
×
136922
≡
160788
(
mod
166667
)
{\displaystyle n=21057\times 136922\equiv 160788{\pmod {166667}}}
n
=
21057
×
303589
≡
660789
(
mod
166667
)
{\displaystyle n=21057\times 303589\equiv 660789{\pmod {166667}}}
n
=
21057
×
470256
≡
160788
(
mod
166667
)
{\displaystyle n=21057\times 470256\equiv 160788{\pmod {166667}}}
n
=
21057
×
636923
≡
660789
(
mod
166667
)
{\displaystyle n=21057\times 636923\equiv 660789{\pmod {166667}}}
n
=
21057
×
803590
≡
160788
(
mod
166667
)
{\displaystyle n=21057\times 803590\equiv 160788{\pmod {166667}}}
n
=
21057
×
970257
≡
660789
(
mod
166667
)
{\displaystyle n=21057\times 970257\equiv 660789{\pmod {166667}}}
Nu is
5
160789
=
686596
(
mod
1000003
)
{\displaystyle 5^{160789}=686596{\pmod {1000003}}}
en
5
660789
=
262682
(
mod
1000003
)
{\displaystyle 5^{660789}=262682{\pmod {1000003}}}
Dus
n
=
660789
{\displaystyle n=660789}
(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.
