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}$ .

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.

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".

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

• 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.