Pollard's rho algorithm for logarithms is an algorithm introduced byJohn Pollard in 1978 to solve thediscrete logarithm problem, analogous toPollard's rho algorithm to solve theinteger factorization problem.

The goal is to compute${\displaystyle \gamma }$ such that${\displaystyle {\alpha }^{\gamma }=\beta }$, where${\displaystyle \beta }$ belongs to acyclic group${\displaystyle G}$ generated by${\displaystyle \alpha }$. The algorithm computesintegers${\displaystyle a}$,${\displaystyle b}$,${\displaystyle A}$, and${\displaystyle B}$ such that${\displaystyle {\alpha }^a{\beta }^b={\alpha }^A{\beta }^B}$. If the underlyinggroup is cyclic oforder${\displaystyle n}$, by substituting${\displaystyle \beta }$ as${\displaystyle {\alpha }^{\gamma }}$ and noting that two powers are equalif and only if the exponents are equivalent modulo the order of the base, in this case modulo${\displaystyle n}$, we get that${\displaystyle \gamma }$ is one of the solutions of the equation${\displaystyle (B-b)\gamma =(a-A)(\mathrm{mod}n)}$. Solutions to this equation are easily obtained using theextended Euclidean algorithm.

To find the needed${\displaystyle a}$,${\displaystyle b}$,${\displaystyle A}$, and${\displaystyle B}$ the algorithm usesFloyd's cycle-finding algorithm to find a cycle in the sequence${\displaystyle x_i={\alpha }^{a_i}{\beta }^{b_i}}$, where thefunction${\displaystyle 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${\displaystyle \sqrt{\frac{\pi n}{8}}}$ after${\displaystyle \sqrt{\frac{\pi n}{8}}}$ steps. One way to define such a function is to use the following rules:Partition${\displaystyle G}$ into threedisjoint subsets${\displaystyle S_0}$,${\displaystyle S_1}$, and${\displaystyle S_2}$ of approximately equal size using ahash function. If${\displaystyle x_i}$ is in${\displaystyle S_0}$ then double both${\displaystyle a}$ and${\displaystyle b}$; if${\displaystyle x_i\in S_1}$ then increment${\displaystyle a}$, if${\displaystyle x_i\in S_2}$ then increment${\displaystyle b}$.

Let${\displaystyle G}$ be acyclic group of order${\displaystyle n}$, 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

input:a: a generator ofGb: an element ofGoutput: An integerx such thatax =b, or failureInitialisei ← 0,a0 ← 0,b0 ← 0,x0 ← 1 ∈Gloopi ←i + 1xi ←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)whilexi ≠x2ir ←bi −b2iif r = 0return failurereturnr−1(a2i −ai) modn

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 followingC++ program:

#include<stdio.h>constintn=1018,N=n+1;/* N = 1019 -- prime     */constintalpha=2;/* generator             */constintbeta=5;/* 2^{10} = 1024 = 5 (N) */voidnew_xab(int&x,int&a,int&b){switch(x%3){case0:x=x*x%N;a=a*2%n;b=b*2%n;break;case1:x=x*alpha%N;a=(a+1)%n;break;case2:x=x*beta%N;b=(b+1)%n;break;}}intmain(void){intx=1,a=0,b=0;intX=x,A=a,B=b;for(inti=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;}return0;}

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 41249   101 680 377   860 300 41350   505 680 378   101 300 41551  1010 681 378  1010 301 416

That is${\displaystyle 2^{681}{5}^{378}=1010=2^{301}{5}^{416}(\mathrm{mod}1019)}$ and so${\displaystyle (416-378)\gamma =681-301(\mathrm{mod}1018)}$, for which${\displaystyle {\gamma }_1=10}$ is a solution as expected. As${\displaystyle n=1018}$ is notprime, there is another solution${\displaystyle {\gamma }_2=519}$, for which${\displaystyle 2^{519}=1014=-5(\mathrm{mod}1019)}$ holds.

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

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

• Logarithms
• Number theoretic algorithms

• Articles with short description
• Short description is different from Wikidata