Content deleted Content added
Citation bot (talk | contribs) Add: title. Changed bare reference to CS1/2. | Use this bot. Report bugs. | Suggested by BrownHairedGirl | Linked from User:BrownHairedGirl/Articles_with_bare_links | #UCB_webform_linked 973/2195 |
linking |
||
Line 1:
In [[computational number theory]] and [[computer algebra|computational algebra]], '''Pollard's kangaroo algorithm''' (also '''Pollard's lambda algorithm''', see [[#Naming|Naming]] below) is an [[algorithm]] for solving the [[discrete logarithm]] problem. The algorithm was introduced in 1978 by the number theorist [[John Pollard (mathematician)|J. M. Pollard]], in the same paper as his better-known [[Pollard's rho algorithm for logarithms|Pollard's rho algorithm]] for solving the same problem.<ref>J. Pollard, ''[https://www.ams.org/journals/mcom/1978-32-143/S0025-5718-1978-0491431-9/S0025-5718-1978-0491431-9.pdf Monte Carlo methods for index computation (mod p)]'', Mathematics of Computation, Volume 32, 1978</ref> 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.
==Algorithm==
Line 35:
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<ref>J. M. Pollard, ''[https://link.springer.com/content/pdf/10.1007/s001450010010.pdf 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 (algorithm)|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]]".
The second 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 shorter stroke of the letter lambda corresponds to the sequence <math>\{x_i\}</math>, since it starts from the position b to the right of x. Accordingly, the longer 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.
| |||