Pollard's kangaroo algorithm: Difference between revisions

Revision as of 07:49, 8 April 2020

Revision as of 20:34, 31 August 2020

Line 30:

==Complexity==

Pollard gives the time complexity of the algorithm as <math>{\scriptstyle O(\sqrt{b-a})}</math>, based on a probabilistic argument which follows from the assumption that ''f'' acts pseudorandomly. When the size of the set {''a'',&nbsp;…,&nbsp;''b''} to be searched is measured in [[Binary digits|bits]], as is normal in [[Computational complexity theory|complexity theory]], the set has size log(''b''&thinsp;&minus;&thinsp;''a''), and so the algorithm's complexity is <math>{\scriptstyle O(\sqrt{b-a}) = O(2^{\frac{1}{2}\log(b-a)/2})}</math>, which is exponential in the problem size. For this reason, Pollard's lambda algorithm is considered an [[exponential time]] algorithm. For an example of a [[subexponential time]] discrete logarithm algorithm, see the [[index calculus algorithm]].

==Naming==