Pollard's kangaroo algorithm

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 John M. Pollard, in the same paper as his better-known Pollard's 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 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, one seeks such that . The lambda algorithm allows one to search for in some interval . One may search the entire range of possible logarithms by setting and .

Choose a set of positive integers of mean roughly and define a pseudorandom map .
Choose an integer and compute a sequence of group elements according to:
Compute Observe that:
Begin computing a second sequence of group elements according to: and a corresponding sequence of integers according to: Observe that:
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 , using a probabilistic argument based on the assumption that acts pseudorandomly. Since can be represented using bits, this is exponential in the problem size (though still a significant improvement over the trivial brute-force algorithm that takes time ). 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".

Choose a set of positive integers of mean roughly and define a pseudorandom map .
Choose an integer and compute a sequence of group elements according to:
Compute Observe that:
Begin computing a second sequence of group elements according to: and a corresponding sequence of integers according to: Observe that:
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 , using a probabilistic argument based on the assumption that acts pseudorandomly. Since can be represented using bits, this is exponential in the problem size (though still a significant improvement over the trivial brute-force algorithm that takes time ). 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".

Chat with Graph Search