Pollard's kangaroo algorithm

In mathematics, specifically computational number theory and computational algebra, Pollard's lambda algorithm (aka Pollard's kangaroo algorithm, see Naming below) is an algorithm for solving the discrete logarithm problem. The algorithm was introducted in 1978 by the accomplished number theorist J. M. Pollard, in the same paper ^[1] as his better-known rho 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 ${\displaystyle p}$, the algorithm is in fact a generic discrete logarithm algorithm - it will work in finite cyclic group.

The algorithm

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\}}$  of ${\displaystyle Z_{n}}$ . We may search the entire range of possible logarithms by setting ${\displaystyle a=0}$  and ${\displaystyle b=p-1}$ , although in this case Pollard's rho algorithm is more efficient. We proceed as follows:

1. Choose a set ${\displaystyle S}$  of integers and define a pseudorandom map ${\displaystyle f:G\rightarrow S}$ .

2. Choose an integer ${\displaystyle N}$  and compute a sequence of group elements ${\displaystyle \{x_{0},x_{1},\ldots ,x_{N}\}}$  according to:

• ${\displaystyle x_{0}=\alpha ^{b}}$ 
• ${\displaystyle x_{i+1}=x_{i}\alpha ^{f(x_{i})}}$  for ${\displaystyle i=0,1,\ldots ,N-1}$ 

3. Compute

${\displaystyle d=\sum _{i=0}^{i}={N-1}f(x_{i})}$ .

Observe that:

${\displaystyle x_{N}=x_{0}\alpha ^{d}=\alpha ^{b+d}}$ .

4. Begin computing a second sequence of group elements ${\displaystyle \{y_{0},y_{1},\ldots \}}$  according to:

• ${\displaystyle y_{0}=\beta }$ 
• ${\displaystyle y_{i+1}=y_{i}\alpha ^{f(y_{i})}}$  for ${\displaystyle i=0,1,\ldots ,N-1}$ 

and a corresponding sequence of integers ${\displaystyle \{d_{0},d_{1},\ldots \}}$  according to:

${\displaystyle d_{n}=\sum _{i=0}^{n-1}f(y_{i})}$ .

Observe that:

${\displaystyle y_{i}=y_{0}\alpha _{i}^{d}=\beta \alpha ^{d_{i}}}$  for ${\displaystyle i=0,1,\ldots ,N-1}$ 

5. Stop computing terms of ${\displaystyle \{y_{i}\}}$  and ${\displaystyle \{d_{i}\}}$  when either of the following conditions are met:

A ${\displaystyle y_{i}=x_{N}}$  for some ${\displaystyle j}$ . If the sequences ${\displaystyle \{x_{i}\}}$  and ${\displaystyle \{y_{j}\}}$  "collide" in this manner, then we have:

${\displaystyle x_{N}=y_{j}\Rightarrow \alpha ^{b+d}=\beta \alpha ^{d_{j}}\Rightarrow \beta =\alpha ^{b+d-d_{j}}\Rightarrow x\equiv b+d-d_{j}{\pmod {p}}}$ 

and so we are done.

B ${\displaystyle d_{i}>b-a+d}$ . If this occurs, then the algorithm has failed to find ${\displaystyle x}$ . Subsequent attempts can be made by changing the choice of ${\displaystyle S}$  and/or ${\displaystyle f}$ .

Complexity

Pollard gives the time complexity of the algorithm as ${\displaystyle O({\sqrt {(b-a)}})}$ , based on a probabilistic argument which follows from the assumption that ${\displaystyle f}$  acts pseudorandomly. Note that when the size of the set ${\displaystyle \{a,\ldots ,b\}}$  to be searched is measured in bits, as is normal in complexity theory, the set has size ${\displaystyle \log(b-a)}$ , and so the algorithm's complexity is ${\displaystyle O({\sqrt {\log(b-a)}})=O(e^{{\frac {1}{2}}\log(b-a)})}$ , which is exponential in the problem size. For this reason, Pollard's lambda algorithm is considered an exponential time algorithm. For an example of a subexponential time discrete logarithm algorithm, see the index calculs algorithm.

Naming

The algorithm is well known by two names.

The first is "Pollard's lambda algorithm". Much like the name of another of Pollard's discrete logarithm algorithms, Pollard's rho algorithm, this name refers to the similarity between a visualisation of the algorithm and the Greek letter lambda (${\displaystyle \lambda }$ ). The longer stroke of the letter lambda corresponds to the sequence ${\displaystyle \{x_{i}\}}$ . The shorter stroke corresponds to the sequence ${\displaystyle \{y_{i}\}}$ , which "collides with" the first sequence (just like the strokes of a lambda intersect) and then follows it subsequently.

The second is "Pollard's kangaroo algorithm". This name is a reference to an analogy used in the paper presenting the algorithm, where the algorithm is explained in terms of using a tame kangaroo to trap a wild kangaroo. Pollard has explained ^[2] that this analogy was inspired by a "fascinating " article published in the same issue of Scientific American as an exposition of the well known RSA public key cryptosystem. The article ^[3] described an experiment in which a kangaroo's "energetic cost of locomation, measured in terms of oxygen consumption at various speeds, was determined by placing kangaroos on a treadmill".

Pollard has expressed a preference for the name "kangaroo algorithm"^{[citation needed]}, as this avoids confusion over the fact that some parallel versions of his rho algorithm have also been named "lambda algorithms".

See also

• Discrete logarithm problem
• Pollard's rho algorithm for logarithms

References

1. J. Pollard, Monte Carlo methods for index computation mod p, Mathematics of Computation, Volume 32, 1978
2. J. M. Pollard, Kangaroos, Monopoly and Discrete Logarithms, Jounral of Cryptology, Volume 13, pp 437-447, 2000
3. T. J. Dawson, Kangaroos, Scientific American, August 1977, pp. 78-89