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 $\gamma$ such that $\alpha ^ \gamma = \beta$ , where $\beta$ belongs to a cyclic group $G$ generated by $\alpha$ . The algorithm computes integers $a$ , $b$ , $A$ , and $B$ such that $\alpha^a \beta^b = \alpha^A \beta^B$ . If the underlying group is cyclic of order $n$ , by substituting $\beta$ as ${\alpha}^{\gamma}$ and noting that two powers are equal if and only if the exponents are equivalent modulo the order of the base, in this case modulo $n$ , we get that $\gamma$ is one of the solutions of the equation $(B-b) \gamma = (a-A) \pmod n$ . Solutions to this equation are easily obtained using the extended Euclidean algorithm.

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 = \alpha^{a_i} \beta^{b_i}$ , where the function $f: x_i \mapsto x_{i+1}$ is assumed to be random-looking and thus is likely to enter into a loop of approximate length $\sqrt{\frac{\pi n}{8}}$ after $\sqrt{\frac{\pi n}{8}}$ steps. One way to define such a function is to use the following rules: Partition $G$ into three disjoint subsets $S_0$ , $S_1$ , and $S_2$ of approximately equal size using a hash function. If $x_i$ is in $S_0$ then double both $a$ and $b$ ; if $x_i \in S_1$ then increment $a$ , if $x_i \in S_2$ then increment $b$ .

Algorithm

Let $G$ be a cyclic group of order $n$ , and given $\alpha, \beta\in G$ , and a partition $G = S_0\cup S_1\cup S_2$ , let $f:G\to G$ be the map

: $f(x) = \begin{cases}
\beta x & x\in S_0\\
x^2 & x\in S_1\\
\alpha x & x\in S_2
\end{cases}$

and define maps $g:G\times\mathbb{Z}\to\mathbb{Z}$ and $h:G\times\mathbb{Z}\to\mathbb{Z}$ by

: $\begin{align}
g(x,k) &= \begin{cases}
k & x\in S_0\\
2k \pmod {n} & x\in S_1\\
k+1 \pmod {n} & x\in S_2
\end{cases}
\\
h(x,k) &= \begin{cases}
k+1 \pmod {n} & x\in S_0\\
2k \pmod {n} & x\in S_1\\
k & x\in S_2
\end{cases}
\end{align}$

input: a: a generator of G

b: an element of G

output: An integer x such that a^x = b, or failure

Initialise i ← 0, a₀ ← 0, b₀ ← 0, x₀ ← 1 ∈ G

loop

i ← i + 1

x_i ← f(x_i−1),

a_i ← g(x_i−1, a_i−1),

b_i ← h(x_i−1, b_i−1)

x_2i−1 ← f(x_2i−2),

a_2i−1 ← g(x_2i−2, a_2i−2),

b_2i−1 ← h(x_2i−2, b_2i−2)

x_2i ← f(x_2i−1),

a_2i ← g(x_2i−1, a_2i−1),

b_2i ← h(x_2i−1, b_2i−1)

while x_i ≠ x_2i

r ← b_i − b_2i

if r = 0 return failure

return r⁻¹(a_2i − a_i) mod n

Example

Consider, 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:

include

const int n = 1018, N = n + 1; /* N = 1019 -- prime */

const int alpha = 2; /* generator */

const int beta = 5; /* 2^{10} = 1024 = 5 (N) */

void new_xab(int& x, int& a, int& b) {

switch (x % 3) {

case 0: x = x * x % N; a = a*2 % n; b = b*2 % n; break;

case 1: x = x * alpha % N; a = (a+1) % n; break;

case 2: x = x * beta % N; b = (b+1) % n; break;

}

int main(void) {

int x = 1, a = 0, b = 0;

int X = x, A = a, B = b;

for (int i = 1; i < n; ++i) {

new_xab(x, a, b);

new_xab(X, A, B);

printf("%3d %4d %3d %3d %4d %3d %3d\n", i, x, a, b, X, A, B);

if (x == X) break;

}

return 0;

}

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

That is $2^{681} 5^{378} = 1010 = 2^{301} 5^{416} \pmod{1019}$ and so $(416-378)\gamma = 681-301 \pmod{1018}$ , for which $\gamma_1=10$ is a solution as expected. As $n=1018$ is not prime, there is another solution $\gamma_2=519$ , for which $2^{519} = 1014 = -5\pmod{1019}$ holds.

Complexity

The running time is approximately $\mathcal{O}(\sqrt{n})$ . If used together with the Pohlig–Hellman algorithm, the running time of the combined algorithm is $\mathcal{O}(\sqrt{p})$ , where $p$ is the largest prime factor of $n$ .

References

{{cite journal |first=J. M. |last=Pollard |title=Monte Carlo methods for index computation (mod p) |journal=Mathematics of Computation |volume=32 |year=1978 |issue=143 |pages=918–924 |doi= 10.2307/2006496 |jstor=2006496 }}
{{cite book |first1=Alfred J. |last1=Menezes |first2=Paul C. |last2=van Oorschot |first3=Scott A. |last3=Vanstone |chapter-url=https://cacr.uwaterloo.ca/hac/about/chap3.pdf |title=Handbook of Applied Cryptography |chapter=Chapter 3 |year=2001 }}

Category:Logarithms

Category:Number theoretic algorithms