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


select a smoothness bound $B$
define ${\displaystyle M=\prod _{{\text{primes}}~q\leq B}q^{\lfloor \log _{q}{B}\rfloor }} $ (note: explicitly evaluating $M$ may not be necessary)
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)
compute $g = \operatorname{gcd}(a^M − 1, n)$ (note: exponentiation can be done modulo n)
if $1 &lt; g &lt; n$ then return $g$
if $g = 1$ then select a larger $B$ and go to step 2 or return failure
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 &lt; 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 &lt; \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)$.