This page uses content from Wikipedia and is licensed under CC BY-SA.

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 ^{[1]} 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 is a finite cyclic group of order which is generated by the element , and we seek to find the discrete logarithm of the element to the base . In other words, we seek such that . The lambda algorithm allows us to search for in some subset . We may search the entire range of possible logarithms by setting and , although in this case Pollard's rho algorithm for logarithms is more efficient. We proceed as follows:

1. Choose a set of integers and define a pseudorandom map .

2. Choose an integer and compute a sequence of group elements according to:

3. Compute

- .

Observe that:

4. Begin computing a second sequence of group elements according to:

and a corresponding sequence of integers according to:

- .

Observe that:

5. Stop computing terms of and when either of the following conditions are met:

- A) for some . If the sequences and "collide" in this manner, then we have:
- and so we are done.

- B) . If this occurs, then the algorithm has failed to find . Subsequent attempts can be made by changing the choice of and/or .

Pollard gives the time complexity of the algorithm as , based on a probabilistic argument which follows from the assumption that *f* acts pseudorandomly. Note that when the size of the set {*a*, …, *b*} to be searched is measured in bits, as is normal in complexity theory, the set has size log(*b* − *a*), and so the algorithm's complexity is , 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 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^{[2]} 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^{[3]} 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 (). The shorter stroke of the letter lambda corresponds to the sequence , since it starts from the position b to the right of x. Accordingly, the longer stroke corresponds to the sequence , 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",^{[4]} as this avoids confusion with some parallel versions of his rho algorithm, which have also been called "lambda algorithms".

**^**J. Pollard,*Monte Carlo methods for index computation mod p*, Mathematics of Computation, Volume 32, 1978**^**J. M. Pollard,*Kangaroos, Monopoly and Discrete Logarithms*, Journal of Cryptology, Volume 13, pp 437-447, 2000**^**T. J. Dawson,*Kangaroos*, Scientific American, August 1977, pp. 78-89**^**[sites.google.com]