Pollard's kangaroo algorithm: Difference between revisions

Revision as of 17:55, 1 October 2022

Revision as of 17:56, 1 October 2022

Line 1:

{{Short description|I don't understand why does cryptography have so much math}}

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.