1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.
$\endgroup$
10
  • $\begingroup$ 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$? $\endgroup$
    – user93353
    Jun 10 at 4:13
  • $\begingroup$ 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? $\endgroup$
    – user93353
    Jun 10 at 4:21
  • $\begingroup$ 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? $\endgroup$
    – SSA
    Jun 10 at 4:25
  • $\begingroup$ I can't think of any option at all :-) I am a noob. $\endgroup$
    – user93353
    Jun 10 at 4:31
  • $\begingroup$ you have power of 2 is 8, for 3 is 2, etc - what do you mean for 3 is 2?. $\endgroup$
    – user93353
    Jun 10 at 4:33

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.