Pollard's rho algorithm for logarithms

Let ${\displaystyle G}$ be a cyclic group of order ${\displaystyle p}$, and given ${\displaystyle \alpha ,\beta \in G}$, and a partition ${\displaystyle G=S_{0}\cup S_{1}\cup S_{2}}$, let ${\displaystyle f:G\to G}$ be the map and define maps ${\displaystyle g:G\times \mathbb {Z} \to \mathbb {Z} }$ and ${\displaystyle h:G\times \mathbb {Z} \to \mathbb {Z} }$ by

${\displaystyle {\begin{aligned}g(x,n)&={\begin{cases}n&x\in S_{0}\\2n{\pmod {p}}&x\in S_{1}\\n+1{\pmod {p}}&x\in S_{2}\end{cases}}\\h(x,n)&={\begin{cases}n+1{\pmod {p}}&x\in S_{0}\\2n{\pmod {p}}&x\in S_{1}\\n&x\in S_{2}\end{cases}}\end{aligned}}}$

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(xi-1), 
    ai ← g(xi-1, ai-1), 
    bi ← h(xi-1, bi-1)

    x2i ← f(f(x2i-2)), 
    a2i ← g(f(x2i-2), g(x2i-2, a2i-2)), 
    b2i ← h(f(x2i-2), h(x2i-2, b2i-2))

    if xi = x2i then
        r ← bi - b2i
        if r = 0 return failure
        x ← r−1(a2i - ai) mod p
        return x
    else // xi ≠ x2i
        i ← i + 1
    end if
end loop

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

#include <stdio.h>

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);
    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 ${\displaystyle 2^{681}5^{378}=1010=2^{301}5^{416}{\pmod {1019}}}$ and so ${\displaystyle (416-378)\gamma =681-301{\pmod {1018}}}$, for which ${\displaystyle \gamma _{1}=10}$ is a solution as expected. As ${\displaystyle n=1018}$ is not prime, there is another solution ${\displaystyle \gamma _{2}=519}$, for which ${\displaystyle 2^{519}=1014=-5{\pmod {1019}}}$ holds.

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

• Pollard, J. M. (1978). "Monte Carlo methods for index computation (mod p)". Mathematics of Computation. 32 (143): 918–924. doi:10.2307/2006496.
• Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (2001). "Chapter 3" (PDF). Handbook of Applied Cryptography.