# Why is pollard rho's expected runtime O(sqrt(n)) not O(sqrt(n) * log(n))?

I understand by the birthday problem, the algorithm will expect to take $$\mathcal{O}(\sqrt{N})$$ times to find a cycle. However, one of the steps involves computing the $$\gcd(\mid x-y \mid, N)$$, which, I assume, uses the euclidean algorithm, which is $$\mathcal{O}(\log(N))$$. So shouldn't it run in $$\mathcal{O}(\sqrt(N) * \log(N))$$?

https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

• Each application of $g$ also has quite likely a similar cost as the gcd, since it also includes a modulo, which is a lot more complex than additions or multiplications. Going into that is a lot more complex than assuming the base cost 1 for $g$ and the gcd.
– tylo
Commented Jun 13, 2022 at 5:48

Ok, this needs a little deeper answer.

What Wikipedia gives as $$\mathcal{O}(\sqrt(N))$$ is the expected number of iterations to notice the repetition in $$N$$ element set. It is not about the actual cost of the algorithm. Just for the finding the first equality (epact).

If we look at the loop the base algorithm ( not the improvements)

    while d = 1:
x ← g(x)
y ← g(g(y))
d ← gcd(|x - y|, n)


It means that we have 3 evaluations of $$g$$ to the modulo and one GCD. The choice of $$g$$ affects this cost, too.

Galbraith, Steven D gave a rigorous analysis of Pollard rho on their book,

• (Heuristic 14.2.9). (This is based of the Harris' analysis on the distribution of the cycles) The expected value for the first repetition (epact) is $$\pi^2/ 12 \sqrt{\pi N /2} \approx 0.823 \sqrt{\pi N /2}$$.

• (Heuristic 14.2.10) The expected value of the epact is $$(0.823+\mathcal{o}(1)) \sqrt{\pi N /2}$$

And the below theorem gives the result based on the above

• Theorem. Let the notation be as above and assume Heuristic 14.2.10. Then the $$rho$$ algorithm with Floyd cycle finding has an expected running time of $$(3.093 + \mathcal{o}(1))\sqrt{N}$$ group operations. The probability the algorithm fails is negligible.

There are improvements of the algorithm and the analysis. One can see them on subsequent pages from the book.