Pollard's kangaroo algorithm

In computational number theory and computational algebra, Pollard's kangaroo algorithm (also Pollard's lambda algorithm, see Naming below) is an algorithm for solving the discrete logarithm problem. The algorithm was introduced in 1978 by the number theorist J. M. Pollard, in the same paper as his better-known ρ algorithm for solving the same problem. Although Pollard described the application of his algorithm to the discrete logarithm problem in the multiplicative group of units modulo a prime p, it is in fact a generic discrete logarithm algorithm—it will work in any finite cyclic group.

Suppose ${\displaystyle G}$ is a finite cyclic group of order ${\displaystyle n}$ which is generated by the element ${\displaystyle \alpha }$, and we seek to find the discrete logarithm ${\displaystyle x}$ of the element ${\displaystyle \beta }$ to the base ${\displaystyle \alpha }$. In other words, we seek ${\displaystyle x\in Z_{n}}$ such that ${\displaystyle \alpha ^{x}=\beta }$. The lambda algorithm allows us to search for ${\displaystyle x}$ in some subset ${\displaystyle \{a,\ldots ,b\}\subset Z_{n}}$. We may search the entire range of possible logarithms by setting ${\displaystyle a=0}$ and ${\displaystyle b=n-1}$, although in this case Pollard's rho algorithm is more efficient. We proceed as follows:

...
Wikipedia