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.
Contents
The algorithm
Suppose
1. Choose a set
2. Choose an integer
3. Compute
Observe that:
4. Begin computing a second sequence of group elements
and a corresponding sequence of integers
Observe that:
5. Stop computing terms of
Complexity
Pollard gives the time complexity of the algorithm as
Naming
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 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 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 (
Pollard has expressed a preference for the name "kangaroo algorithm", as this avoids confusion with some parallel versions of his rho algorithm, which have also been called "lambda algorithms".