Pollard's $(p - 1)$ factorization method runtime

Question

Wondering if anyone knows a good reference for Pollard's $p-1$ algorithm's runtime? I was looking on the Wikipedia page and the runtime cited there is $\mathcal{O}(B\cdot \log B\cdot \log^2 n)$. However, I can't find any reference on the Wikipedia page to this.

Where / how is this result proven?

Answer 1

The $p-1$ method finds factors $p$ of an odd $n$ for which $p-1$ divides only (powers of) primes smaller than some user-selected bound $B$. It does this by computing $$ \gcd(2^M - 1, n), $$ where $M = \mathrm{lcm}([1, 2, \dots, B]) = 2^{\lfloor \log_2 B \rfloor}\cdot 3^{\lfloor \log_3 B \rfloor} \dots$. Note that the exponentiation $2^M - 1$ can (and should!) be performed modulo $n$. We can split the computation into three steps:

• Find the primes up to $B$. Using the sieve of Eratosthenes, this takes time $O(B \log \log B)$. This only needs to be (pre)computed once, regardless of which $n$ we're factoring.
• Compute $2^M - 1 \bmod n$. Instead of computing $M$ explicitly, one may opt to exponentiate $2$ by $2^{\lfloor \log_2 B \rfloor}$, then by $3^{\lfloor \log_3 B \rfloor}$, etc. Each exponent has $O(\log_2 B)$ bits, and there are approximately $B / \log B$ primes, by the prime number theorem. This gives us an exponent of $B / \log B \cdot \log_2 B = B / \log 2$ bits, which leads to $O(B)$ multiplications modulo $n$ using binary exponentiation.
• A final GCD of integers at most $n$ sized, which costs at most $\log n$ multiplications of $n$-sized integers.

Unless $B$ is very small, the cost will be dominated by the second step, which has complexity $O(B \cdot \log n \cdot \log \log n)$ using fast multiplication, or $O(B \cdot (\log n)^2)$ using schoolbook multiplication. Wikipedia's bound appears to be the complexity of the variant which uses $M = B! = O(2^{B \log B})$ as the exponent, instead of $M = \mathrm{lcm}([1, 2, \dots, B])$.