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
    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$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .