Pollard's kangaroo algorithm: Difference between revisions

Revision as of 13:36, 24 August 2007

Revision as of 01:38, 25 August 2007

Line 1:

In mathematics, specifically [[computational number theory]] and [[computational algebra]], '''Pollard's lambda algorithm''' (aka '''Pollard's kangaroo algorithm''', see [[#Naming|Naming]] below) is an [[algorithm]] for solving the [[discrete logarithm problem]]. The algorithm was introducted in 1978 by the accomplished number theorist J. M. Pollard, in the same paper <ref>J. Pollard, ''Monte Carlo methods for index computation mod p'', Mathematics of Computation, Volume 32, 1978</ref> as his better-known [[Pollard's rho algorithm for logarithms|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 <math>p</math>, the algorithm is in fact a generic discrete logarithm algorithm - it will work in finite cyclic group.

==The algorithm==

Line 29:

The first is "Pollard's lambda algorithm". Much like the name of another of Pollard's discrete logarithm algorithms, [[Pollard's rho algorithm for logarithms|Pollard's rho algorithm]], this name refers to the similarity between a visualisation of the algorithm and the [[Greek letter]] [[lambda]] (<math>\lambda</math>). The longer stroke of the letter lambda corresponds to the sequence <math>\{x_i\}</math>. The shorter stroke corresponds to the sequence <math>\{y_i\}</math>, which "collides with" the first sequence (just like the strokes of a lambda intersect) and then follows it subsequently.

The second 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 <ref>J. M. Pollard, ''Kangaroos, Monopoly and Discrete Logarithms'', Jounral of Cryptology, Volume 13, pp 437-447, 2000</ref> that this analogy was inspired by a scientific"fascinating paper" article published in the same issue of Scientific American as an exposition of the well known [[RSA]] [[public key cryptosystem]]{{fact}}. The paperarticle <ref>T. J. Dawson, Kangaroos, Scientific american, August 1977, pp. 78-89</ref> described an experiment in which thea respirationkangaroo's "energetic cost of kangarooslocomation, measured in terms of oxygen consumption at various speeds, was studieddetermined by placing themkangaroos on treadmillsa treadmill".

Pollard has expressed a preference for the name "kangaroo algorithm"{{fact}}, as this avoids confusion over the fact that some parallel versions of his [[Pollard's rho algorithm for logarithms|rho algorithm]] have also been named "lambda algorithms".