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 ${\displaystyle \gamma }$ such that ${\displaystyle \alpha ^{\gamma }=\beta }$, where ${\displaystyle \beta }$ belongs to a cyclic 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}}$. If the underlying group is cyclic of order ${\displaystyle n}$, by substituting ${\displaystyle \beta }$ as ${\displaystyle {\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 ${\displaystyle n}$, we get that ${\displaystyle \gamma }$ is one of the solutions of the equation ${\displaystyle (B-b)\gamma =(a-A){\pmod {n}}}$. Solutions to this equation are easily obtained using the extended Euclidean algorithm.

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 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 three disjoint subsets ${\displaystyle S_{0}}$, ${\displaystyle S_{1}}$, and ${\displaystyle S_{2}}$ of approximately equal size using a hash 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}$.