2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ This might help Pollard’s p-1 and Lenstra’s factoring algorithms $\endgroup$ – kelalaka Aug 19 at 18:51
  • $\begingroup$ 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. $\endgroup$ – Dead_Ling0 Aug 19 at 19:43
  • $\begingroup$ 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. $\endgroup$ – kelalaka Aug 19 at 19:45
2
$\begingroup$

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

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