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

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$$?

• $${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.
• I already understand what you explained above - about using fermat's to prove 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 ${k!}$ -i.e. trying factorials work for finding a suitable $L$? – user93353 Jun 10 at 4:13
• Why is factorial a better choice for finding $L$? Or to be honest, I don't even get why it's a choice at all in the first place? – user93353 Jun 10 at 4:21
• you have power of 2 is 8, for 3 is 2, etc - what do you mean for 3 is 2?. – user93353 Jun 10 at 4:33