Pollard's kangaroo algorithm: Difference between revisions

Revision as of 20:34, 31 August 2020

Revision as of 20:46, 23 November 2020

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, ''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|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.

==Algorithm==