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

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?

• This might help Pollard’s p-1 and Lenstra’s factoring algorithms – kelalaka Aug 19 '19 at 18:51
• Hi i read this when i was looking for some citation, i think she gives some runtimes for parts of the algorithm but not the whole process. – Dead_Ling0 Aug 19 '19 at 19:43
• I think, because, the derivation is not straightforward. Usually, if there were a link, the Wikipedia guys provide it. It is interesting that there is none for this on the article. – kelalaka Aug 19 '19 at 19:45

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