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

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.
• 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$? 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? Jun 10 at 4:21
• when you want to try different numbers which can jump to large values at every step factorial helps, in two cases ,[1] if u have large prime factor or [2] a small prime with large power. so in 10! , you have power of 2 is 8, for 3 is 2, etc.. also I mentioned that this method work well when p-1 is a product of relative small prime. Do you think any better option?
– SSA
Jun 10 at 4:25
• I can't think of any option at all :-) I am a noob. Jun 10 at 4:31
• you have power of 2 is 8, for 3 is 2, etc - what do you mean for 3 is 2?. Jun 10 at 4:33