Contents

Pollard's kangaroo 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, one seeks ${\displaystyle x\in Z_{n}}$ such that ${\displaystyle \alpha ^{x}=\beta }$. The lambda algorithm allows one to search for ${\displaystyle x}$ in some interval ${\displaystyle [a,\ldots ,b]\subset Z_{n}}$. One may search the entire range of possible logarithms by setting ${\displaystyle a=0}$ and ${\displaystyle b=n-1}$.

1. Choose a set ${\displaystyle S}$ of positive integers of mean roughly ${\displaystyle {\sqrt {b-a}}}$ 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})}{\text{ for }}i=0,1,\ldots ,N-1}$

3. Compute

${\displaystyle d=\sum _{i=0}^{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})}{\text{ for }}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 ^{d_{i}}=\beta \alpha ^{d_{i}}{\mbox{ for }}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_{j}=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 {n}}}$

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[edit]

Pollard gives the time complexity of the algorithm as ${\displaystyle O({\sqrt {b-a}})}$, using a probabilistic argument based on the assumption that ${\displaystyle f}$ acts pseudorandomly. Since ${\displaystyle a,b}$ can be represented using ${\displaystyle O(\log b)}$ bits, this is exponential in the problem size (though still a significant improvement over the trivial brute-force algorithm that takes time ${\displaystyle O(b-a)}$). For an example of a subexponential time discrete logarithm algorithm, see the index calculus algorithm.

Naming[edit]

The algorithm is well known by two names.

The first 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^[3] that this analogy was inspired by a "fascinating" article published in the same issue of Scientific American as an exposition of the RSA public key cryptosystem. The article^[4] described an experiment in which a kangaroo's "energetic cost of locomotion, measured in terms of oxygen consumption at various speeds, was determined by placing kangaroos on a treadmill".

The second 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 shorter stroke of the letter lambda corresponds to the sequence ${\displaystyle \{x_{i}\}}$, since it starts from the position b to the right of x. Accordingly, the longer 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.

Pollard has expressed a preference for the name "kangaroo algorithm",^[5] as this avoids confusion with some parallel versions of his rho algorithm, which have also been called "lambda algorithms".

See also[edit]

• Dynkin's card trick
• Kruskal count^[6]
• Rainbow table

References[edit]

Further reading[edit]

• Montenegro, Ravi [at Wikidata]; Tetali, Prasad V. (2010-11-07) [2009-05-31]. How Long Does it Take to Catch a Wild Kangaroo? (PDF). Proceedings of the forty-first annual ACM symposium on Theory of computing (STOC 2009). pp. 553–560. arXiv:0812.0789. doi:10.1145/1536414.1536490. S2CID 12797847. Archived (PDF) from the original on 2023-08-20. Retrieved 2023-08-20.