Computer Security and Cryptography

14.6 POLLARD'S ρ-ALGORITHM [POLLARD, 1978]

The discrete logarithm problem in a group is

Given:    α is a generator in a cyclic group G of order p and β in G;

Find:    γ is in , satisfying α^γ.

Pollard extended the ρ-algorithm described in Chapter 13 for factorization to the DLP.Randomly generate the sequence x₁, x₂, …, x_n with x_i = α^a_iβ^b_i. If

then

If r = (b_i − b_j) and (b_i − b_j)⁻¹ exists, then

so that γ = (b_i − b_j)⁻¹(a_i − a_j).

The same computational issues that appeared in Pollard's ρ-factorization algorithm occur here and a Monte Carlo method for generating the sequence (x_i, a_i, b_i) together with Floyd's cycling finding algorithm comes to the rescue.

Pollard's ρ-algorithm for the DLP follows these steps:

P1.	Partition the group G into three roughly equal subsets G = G0 ∪ G1 ∪ G2. For example, for the cyclic group G = {xn : 0 ≤ n < 509} where is the 509th roots of unity, let Gi = {xn : 0 ≤ n < 50, i = (n modulo 3)}.
P2.	Let α be a generator of G and β = αr; choose a, b ∈ G