# The time complexity of the Wikipedia version of Pollards $(p-1)$ algorithm

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?

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