Pollard's kangaroo algorithm: Difference between revisions

Revision as of 12:44, 26 August 2007

Revision as of 10:36, 27 August 2007

Line 31:

==Complexity==

Pollard gives the time complexity of the algorithm as <math>{\scriptstyle O(\sqrt{(b-a)})}</math>, based on a probabilistic argument which follows from the assumption that ''f'' acts pseudorandomly. Note that when the size of the set {''a'',&nbsp;&hellip;…,&nbsp;''b''} to be searched is measured in [[bits]], as is normal in [[complexity theory]], the set has size log(''b''&thinsp;&minus;&thinsp;''a''), and so the algorithm's complexity is <math>{\scriptstyle O(\sqrt{\log(b-a)}) = O(e^{\frac{1}{2}\log(b-a)})}</math>, 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]].

==Naming==

Line 40:

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'', Journal of Cryptology, Volume 13, pp 437-447, 2000</ref> 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<ref>T. J. Dawson, ''Kangaroos'', Scientific American, August 1977, pp. 78-89</ref> 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".

Pollard has expressed a preference for the name "kangaroo algorithm"{{factFact|date=August 2007}}, as this avoids confusion with some parallel versions of his rho algorithm, which have also been called "lambda algorithms".

==See also==

Line 51:

<references/>

[[Category: Mathematics]]

[[Category: Number theory]]

[[Category: Computer algebra]]

[[Category: Logarithms]]