Content deleted Content added
Added citations for the origin of the name "kangaroo algorithm". Knew I had them around somewhere! |
Very small change to a reference (capitalisation, use of quotes, etc). Where has the option to mark changes as minor gone? |
||
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 "fascinating " article published in the same issue of Scientific American as an exposition of the well known [[RSA]] [[public key cryptosystem]]. The article <ref>T. J. Dawson, ''Kangaroos'', Scientific
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".
| |||