Pollard's kangaroo algorithm is a method in computational number theory and computational algebra for solving the discrete logarithm problem. It was introduced in 1978 by the number theorist John M. Pollard, in the same paper that introduced his better known Pollard's rho algorithm for the same problem. Although Pollard described it for the discrete logarithm problem in the multiplicative group of units modulo a prime, the algorithm is in fact generic and works in any finite cyclic group. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Time Complexity
Time Complexity (category)Sub-Linear / Root Time -- O(sqrt n) 1 Connections
In Field
Source Wikipedia: Pollard's kangaroo algorithm
Sources
1. Wikidata: Pollard's kangaroo algorithm
Wikidata Q1911970, class allow-list match (w-wdresolver-0926)View the Source Wikipedia: Pollard's kangaroo algorithm
Lead section
In computational number theory and computational algebra, Pollard's kangaroo algorithm (also Pollard's lambda algorithm, see Naming below) is an algorithm for solving the discrete logarithm problem.
In Group: Discrete Logarithm and Hidden Subgroup Algorithms, Introduction
In computational number theory and computational algebra, Pollard's kangaroo algorithm (also Pollard's lambda algorithm, see Naming below) is an algorithm for solving the discrete logarithm problem.
In Field: Algorithms and Complexity Theory, Lead sentence
Pollard's kangaroo algorithm (also Pollard's lambda algorithm, see Naming below) is an algorithm for solving the discrete logarithm problem.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.