Pollard's rho algorithm for logarithms: Difference between revisions

Revision as of 00:28, 7 October 2014

Revision as of 18:32, 17 March 2015

Line 104:

==Complexity==

The running time is approximately <math>\mathcal{O}(\sqrt{n})</math>. If used together with the [[Pohlig–Hellman_algorithm|Pohlig-Hellman algorithm]], the running time of the combined algorithm is <math>\mathcal{O}(\sqrt{p})</math>), where <math>p</math> is n'sthe largest prime factor of <math>n</math>.

==References==