Pollard's rho algorithm for logarithms


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 generated by. The algorithm computes integers,, , and such that. If the underlying group is cyclic of order, is one of the solutions of the equation. Solutions to this equation are easily obtained using the Extended Euclidean algorithm.
To find the needed,, , and the algorithm uses Floyd's cycle-finding algorithm to find a cycle in the sequence, where the function is assumed to be random-looking and thus is likely to enter into a loop after approximately steps. One way to define such a function is to use the following rules: Divide into three disjoint subsets of approximately equal size:,, and. If is in then double both and ; if then increment, if then increment.

Algorithm

Let be a cyclic group of order, and given, and a partition, let be the map and define maps and by
input: 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,
ai ← g,
bi ← h
x2i ← f,
a2i ← g, g),
b2i ← h, h)
if xi = x2i then
r ← bi - b2i
if r = 0 return failure
x ← r−1 mod p
return x
else // xi ≠ x2i
i ← i + 1
end if
end loop

Example

Consider, for example, the group generated by 2 modulo . The algorithm is implemented by the following C++ program:

  1. include
const int n = 1018, N = n + 1; /* N = 1019 -- prime */
const int alpha = 2; /* generator */
const int beta = 5; /* 2^ = 1024 = 5 */
void new_xab
int main

The results are as follows :
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 412
49 101 680 377 860 300 413
50 505 680 378 101 300 415
51 1010 681 378 1010 301 416
That is and so, for which is a solution as expected. As is not prime, there is another solution, for which holds.

Complexity

The running time is approximately. If used together with the Pohlig–Hellman algorithm, the running time of the combined algorithm is, where is the largest prime factor of.