Revision as of 12:21, 26 August 2007 edit DavidCBryant (talk \| contribs) Extended confirmed users 3,040 edits m →Naming: Spelling, and style. Removed "well-known" from description of RSA, since it was hardly well-known in 1977. In fact, that was when the NSA tried to suppress its publication. ← Previous edit		Revision as of 12:44, 26 August 2007 edit undo DavidCBryant (talk \| contribs) Extended confirmed users 3,040 edits →Complexity: Regularized in-line expressions, straightened out a wiki-link, and used \scriptstyle to generate smaller .PNGs for in-line TeX. Next edit →
Line 31: ==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 ~~<math>~~''f~~</math>~~'' acts pseudorandomly. Note that when the size of the set ~~<math>\~~{''a'',~~\ldots~~ …, ''b\''}~~</math>~~ to be searched is measured in [[bits]], as is normal in [[complexity theory]], the set has size ~~<math>\~~log(''b-'' − ''a'')~~</math>~~, and so the algorithm's complexity is <math>{\scriptstyle O(\sqrt{\log(b-a)}) = O(e^{\frac{1}{2}\log(b-a)})}</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~~index calculus ~~algorithm\|index calculs~~ algorithm]]. ==Naming==

Pollard's kangaroo algorithm: Difference between revisions