Pollard's kangaroo algorithm: Difference between revisions

Revision as of 17:56, 1 October 2022

Revision as of 11:41, 31 May 2023

Line 30:

==Complexity==

Pollard gives the time complexity of the algorithm as <math>O(\sqrt{b-a})</math>, based onusing a probabilistic argument whichbased follows fromon the assumption that <math>f</math> acts pseudorandomly. When the size of the setSince <math>\{a,\dots, b\}</math> tocan be searchedrepresented is measured in [[bit]]s, as is normal in [[Computational complexity theory|complexity theory]], the set has size <math>\log(b-a)</math>, and so the algorithm's complexity isusing <math>O(\sqrt{b-a})log = O(2^{\log(b-a)/2})</math> bits, whichthis is exponential in the problem size. (though Forstill thisa reason,significant Pollard'simprovement lambdaover algorithmthe istrivial consideredbrute-force analgorithm [[exponentialthat takes time]] algorithm<math>O(b-a)</math>). For an example of a [[subexponential time]] discrete logarithm algorithm, see the [[index calculus algorithm]].

==Naming==