Pollard's rho algorithm for logarithms

Pollard's rho algorithm for logarithms is an algorithm for solving the discrete logarithm problem analogous to Pollard's rho algorithm for solving the Integer factorization problem.

The algorithm computes ${\displaystyle \gamma }$ such that ${\displaystyle \alpha ^{\gamma }=\beta }$, where ${\displaystyle \beta }$ belongs to the group ${\displaystyle G}$ generated by ${\displaystyle \alpha }$. The algorithm computes integers ${\displaystyle a}$, ${\displaystyle b}$, ${\displaystyle A}$, and ${\displaystyle B}$ such that ${\displaystyle \alpha ^{a}\beta ^{b}=\alpha ^{A}\beta ^{B}}$. Assuming, for simplicity, that the underlying group is cyclic of order ${\displaystyle n}$, we can calculate ${\displaystyle \gamma ={\frac {a-A}{B-b}}{\pmod {n}}}$.

To find the needed ${\displaystyle a}$, ${\displaystyle b}$, ${\displaystyle A}$, and ${\displaystyle B}$ the algorithm uses Floyd's cycle-finding algorithm to find a cycle in the sequence ${\displaystyle x_{i}=\alpha ^{a_{i}}\beta ^{b_{i}}}$, where the function ${\displaystyle f:x_{i}\mapsto x_{i+1}}$ is assumed to be random-looking and thus is likely to enter into a loop after approximately ${\displaystyle {\sqrt {\frac {\pi n}{2}}}}$ steps. One way to define such a function is to use the following rules: Divide ${\displaystyle G}$ into three subsets (not necessarily subgroups) of approximately equal size: ${\displaystyle G_{0}}$, ${\displaystyle G_{1}}$, and ${\displaystyle G_{2}}$. If ${\displaystyle x_{i}}$ is in ${\displaystyle G_{0}}$ then double both ${\displaystyle a}$ and ${\displaystyle b}$; if ${\displaystyle x_{i}\in G_{1}}$ then increment ${\displaystyle a}$, if ${\displaystyle x_{i}\in G_{2}}$ then increment ${\displaystyle b}$.

Algorithm

Let ${\displaystyle G}$  be a cyclic group of prime order ${\displaystyle p}$ , and given ${\displaystyle a,b\in G}$ , and a partition ${\displaystyle G=G_{0}\cup G_{1}\cup G_{2}</math,let<math>f:G\to G}$  be a map

${\displaystyle f(x)=\left\{{\begin{matrix}b\cdot x&x\in G_{0}\\x^{2}&x\in G_{1}\\a{\dot {x}}&x\in G_{2}\end{matrix}}\right.}$ 

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

${\displaystyle g(x,n)=\left\{{\begin{matrix}n&x\in G_{0}\\2n{\bmod {p}}&x\in G_{1}\\n+1{\bmod {p}}&x\in G_{2}\end{matrix}}\right.}$ 

${\displaystyle h(x,n)=\left\{{\begin{matrix}n+1{\bmod {p}}&x\in G_{0}\\2n{\bmod {p}}&x\in G_{1}\\n&x\in G_{2}\end{matrix}}\right.}$ 

Inputs a a generator of G, b an element of G

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

1. Initialise a₀ ← 0

   b₀ ← 0

   x₀ ← 1 ∈ G

   i ← 1

2. x_i ← f(x_i-1), a_i ← g(x_i-1,a_i-1), b_i ← h(x_i-1,b_i-1)
3. x_2i ← f(f(x_2i-2)), a_2i ← g(f(x_2i-2),g(x_2i-2,a_2i-2)), b_2i ← h(f(x_2i-2),h(x_2i-2,b_2i-2))
4. If x_i = x_2i then
   1. r ← b_i - b_2i
   2. If r = 0 return failure
   3. x ← r^-1(a_2i - a_i) mod p
   4. return x
5. If x_i ≠ x_2i then i ← i+1, and go to step 2.

Example

Consider, for example, the group generated by 2 modulo ${\displaystyle N=1019}$  (the order of the group is ${\displaystyle n=509}$ ). The algorithm is implemented by the following C++ program:

#include <stdio.h>
const int n = 509, N = 2*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(){
  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); 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 171 376    86 299 412
49   101 171 377   860 300 413
50   505 171 378   101 300 415
51  1010 172 378  1010 301 416

That is ${\displaystyle 2^{172}5^{378}=1010=2^{301}5^{416}{\pmod {1019}}}$  and so ${\displaystyle \gamma ={\frac {172-301}{416-378}}=10{\pmod {509}}}$ , as expected.

References

• J. Pollard, Monte Carlo methods for index computation mod p, Mathematics of Computation, Volume 32, 1978.
• Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of Applied Cryptography, Chapter 3, 2001.