1
$\begingroup$

I am trying to understand the runtime of Pollard's $(p-1)$-algorithm as presented on Wikipedia. There the author writes that it takes $\mathcal{O}(B\log B\log^2n)$ time, but I do not see why.

Here the Wikipedia version:

Inputs: $n$: a composite number

Output: a nontrivial factor of $n$ or failure

  1. select a smoothness bound $B$
  2. define ${\displaystyle M=\prod _{{\text{primes}}~q\leq B}q^{\lfloor \log _{q}{B}\rfloor }} $ (note: explicitly evaluating $M$ may not be necessary)
  3. randomly pick $a$ coprime to $n$ (note: we can actually fix $a$, e.g. if $n$ is odd, then we can always select $a = 2$, random selection here is not imperative)
  4. compute $g = \operatorname{gcd}(a^M − 1, n)$ (note: exponentiation can be done modulo n)
  5. if $1 < g < n$ then return $g$
  6. if $g = 1$ then select a larger $B$ and go to step 2 or return failure
  7. if $g = n$ then select a smaller $B$ and go to step 2 or return failure

I would say that:

The first step takes constant time (clear).

The second step takes $\mathcal{O}(B \log B)$ time due to the distribution of prime numbers.

The third step takes constant time.

Concerning the 4th step: Fast-Exponentiation takes (in the version that I know) $\mathcal{O}(\log M)$ time. The gcd takes $\mathcal{O}(\log n)$ time. (I supposed that $ n < a^M-1$, but I am not sure if this is safe to assume.)

The remaining steps take constant time.

So because of step 2 and 4 I would say that the algorithm takes $\mathcal{O}(B \log B) + \mathcal{O}(\log n) + \mathcal{O}(\log M)$ time. What am I doing wrong?

$\endgroup$
1
$\begingroup$

As you mention, the costliest step is computing $a^M \bmod{n}$. This is done using the repeated squaring algorithm. Each squaring or multiplication modulo $n$ takes time $M(n)$, where $M(n)$ is the time complexity of multiplication.

We can estimate the number of multiplications by $$ \sum_{\text{prime } q \leq B} \frac{\log B}{\log q} \cdot \log q < \pi(B) \log B = O(B). $$ This improves slightly on the Wikipedia estimate of $O(B\log B)$.

The school multiplication algorithm takes time $O(\log^2 n)$, which is how Wikipedia got that factor. But nowadays faster algorithms are known, which run in time $\tilde{O}(\log n)$. So a better estimate on the complexity is $\tilde{O}(B\log n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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