Pollard's rho algorithm for logarithms

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 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==

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 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==