2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – tylo
    Commented Jun 13, 2022 at 5:48

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.