Pollard's rho algorithm for logarithms is an algorithm introduced by John Pollard in 1978 to solve the discrete logarithm problem, analogous to Pollard's rho algorithm to solve the integer factorization problem.
The goal is to compute γ such that α γ = β , where β belongs to a cyclic group G generated by α . The algorithm computes integers a , b , A , and B such that α a β b = α A β B . If the underlying group is cyclic of order n , γ is one of the solutions of the equation ( B − b ) γ = ( a − A ) ( mod n ) .
To find the needed a , b , A , and B the algorithm uses Floyd's cycle-finding algorithm to find a cycle in the sequence x i = α a i β b i , where the function f : x i ↦ x i + 1 is assumed to be random-looking and thus is likely to enter into a loop after approximately π n 2 steps. One way to define such a function is to use the following rules: Divide G into three disjoint subsets of approximately equal size: S 0 , S 1 , and S 2 . If x i is in S 0 then double both a and b ; if x i ∈ S 1 then increment a , if x i ∈ S 2 then increment b .
Let G be a cyclic group of order p, and given α , β ∈ G , and a partition G = S 0 ∪ S 1 ∪ S 2 , let f : G → G be a map
f ( x ) = { β x x ∈ S 0 x 2 x ∈ S 1 α x x ∈ S 2 and define maps g : G × Z → Z and h : G × Z → Z by
g ( x , n ) = { n x ∈ S 0 2 n ( mod p ) x ∈ S 1 n + 1 ( mod p ) x ∈ S 2 h ( x , n ) = { n + 1 ( mod p ) x ∈ S 0 2 n ( mod p ) x ∈ S 1 n x ∈ S 2 Inputs a: a generator of
G,
b: an element of
G Output An integer
x such that
ax =
b, or failure Initialise
a0 ← 0,
b0 ← 0,
x0 ← 1 ∈
G,
i ← 1
loop xi ←
f(
xi-1),
ai ←
g(
xi-1,
ai-1),
bi ←
h(
xi-1,
bi-1)
x2i ←
f(
f(
x2i-2)),
a2i ←
g(
f(
x2i-2),
g(
x2i-2,
a2i-2)),
b2i ←
h(
f(
x2i-2),
h(
x2i-2,
b2i-2))
if xi =
x2i then r ←
bi -
b2i if r = 0
return failure x ←
r−1(
a2i -
ai) mod
p return x else # xi ≠ x2i i ←
i+1,
break loop end if end loopConsider, for example, the group generated by 2 modulo N = 1019 (the order of the group is n = 1018 , 2 generates the group of units modulo 1019). The algorithm is implemented by the following C++ program:
The results are as follows (edited):
i x a b X A B------------------------------ 1 2 1 0 10 1 1 2 10 1 1 100 2 2 3 20 2 1 1000 3 3 4 100 2 2 425 8 6 5 200 3 2 436 16 14 6 1000 3 3 284 17 15 7 981 4 3 986 17 17 8 425 8 6 194 17 19..............................48 224 680 376 86 299 41249 101 680 377 860 300 41350 505 680 378 101 300 41551 1010 681 378 1010 301 416
That is 2 681 5 378 = 1010 = 2 301 5 416 ( mod 1019 ) and so ( 416 − 378 ) γ = 681 − 301 ( mod 1018 ) , for which γ 1 = 10 is a solution as expected. As n = 1018 is not prime, there is another solution γ 2 = 519 , for which 2 519 = 1014 = − 5 ( mod 1019 ) holds.
The running time is approximately O ( n ) . If used together with the Pohlig-Hellman algorithm, the running time of the combined algorithm is O ( p ) , where p is the largest prime factor of n .
