Pollard's p - 1 factorization algo is described in most books as finding a B-smooth p-1, while it's actually trying to find B-powersmooth p - 1. Why?

120 Views Asked by At

In Pollard's $p-1$ algorithm for factoring $N$, you try to find a $L$ such that $p - 1$ divides $L$.

You do this by trying to find a B-Powersmooth $p - 1$ by trying either $n$ = $1$ to $B$, and calculating $n!$ for each & checking $gcd(a^{n!} - 1, N)$. (The exponentiation is done mod N - omitting it for simplicity) Another method instead of using factorial is to use the LCM of the range instead of the factorial.

In each of these, IMHO, you are trying to find a B-Powersmooth $p - 1$. Many books describe it so, but I have also seen a lot of books which describe it as trying to find a B-smooth $p - 1$.

B-smooth & B-powersmooth have different meanings, so why is used interchangeably?

Examples of books which use B-smooth instead of B-powersmooth - Joy of Factoring by Wagstaff, Mathematical Cryptography by Silverman. The Wikipedia article on Pollard's $p - 1$, ans Nigel Smart's book refer to it as B-powersmooth.

So why this confusion?