Editing Pollard's rho algorithm (section)

== Complexity ==
If the pseudorandom number <math>x = g(x)</math> occurring in the Pollard ''ρ'' algorithm were an actual random number, it would follow that success would be achieved half the time, by the [[birthday paradox]] in <math>O(\sqrt p)\le O(n^{1/4})</math> iterations. It is believed that the same analysis applies as well to the actual rho algorithm, but this is a heuristic claim, and rigorous analysis of the algorithm remains open.<ref>{{cite book|title=Mathematics of Public Key Cryptography|first=Steven D.|last=Galbraith|publisher=Cambridge University Press|year=2012|isbn=9781107013926|contribution=14.2.5 Towards a rigorous analysis of Pollard rho|pages=272–273|url=https://books.google.com/books?id=owd76BElvosC&pg=PA272}}.</ref>