Why is factorial used in Pollard's $p - 1$ algorithm?

Question

Why exactly do we use factorial for finding an $L$ which is divisible by $p - 1$?

Pollard's algorithm is about B-powersmooth numbers & not B-smooth numbers. So where exactly does the factorial come in? Factorials aren't done by powering anything - it's just a multiplication of numbers without any exponentiation.

I am referring to Pollard's $p - 1$ algorithm as covered in Silverman's Mathematical Cryptography book - where they check $a^{j!} - 1$ in a loop (with j incrementing) till they find the right $gcd(a^{j!} - 1)$ which leads to a factor.

I understand the part where Fermat's Little Theorem is used to show that L is such that $p-1$ divides $a^L - 1$ & $q-1$ does not divide $a^L - 1$ - my question is not related to that. My question is why/how does trying ${j!}$ (i.e. trying factorials) work for finding a suitable $L$?

Answer 1

Fermat theorem Lies behind this second factorization scheme, known as pollard p-1 method.

• suppose odd composite integer n to be factored has prime divisor n, with the property that p-1 is a product of relatively small primes. Let q be then any integer such that (p-1)|q. For instance q could be either k! or the least common multiple of first k positive integers, where k is taken sufficiently large. select 1<a<p-1
• $${m\equiv a^q \equiv a^{(p-1)j}\equiv 1^j \equiv1(modp)}$$ implies p | (m-1), this forces ${gcd(m-1,n)>1}$
• But it is important to note here is , if ${gcd(m-1,n)=1}$, then one should go back and select the different value of a.
• The method might fail if q (k!) is not taken to be large enough; that is if p-1 contains large prime factor or a small prime occurring to a large power, hence it is better to choose k!,rather than guessing any new large number every time we get ${gcd(m-1,n)=1}$, hence factorial is better choice, and can increase the probability of finding if a factor is large prime factor.