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.

belongs to a cyclic group. The algorithm computes integers. If the underlying group is cyclic of order and noting that two powers are equal if and only if. Solutions to this equation are easily obtained using the extended Euclidean algorithm.

the algorithm uses Floyd's cycle-finding algorithm, where the function steps. One way to define such a function is to use the following rules: Partition into three disjoint subsets of approximately equal size using a hash function.

Algorithm

be a cyclic group be the map

of the result. These maps would be given by

input: a: a generator of G
       b: an element of G
output: An integer x such that ax = b, or failure

Initialise i ← 0, a0 ← 0, b0 ← 0, x0 ← 1 ∈ G

loop
    i ← i + 1

    xi ← f(xi−1),
    ai ← g(xi−1, ai−1),
    bi ← h(xi−1, bi−1)

    x2i−1 ← f(x2i−2),
    a2i−1 ← g(x2i−2, a2i−2),
    b2i−1 ← h(x2i−2, b2i−2)
    x2i ← f(x2i−1),
    a2i ← g(x2i−1, a2i−1),
    b2i ← h(x2i−1, b2i−1)
while xi ≠ x2i

r ← bi − b2i
if r = 0 return failure
return r−1(a2i − ai) mod n

Example

, 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 412
49   101 680 377   860 300 413
50   505 680 378   101 300 415
51  1010 681 378  1010 301 416

is not prime holds.

Complexity

. If used together with the Pohlig–Hellman algorithm is the largest prime factor.

References