Score:1

Crypto

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

user93353

10/9/22, 11:30 PM

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

137

1 + 0

number-theory

pki

factoring

Score:3

Crypto

SSA

10/10/22, 4:08 AM

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.

0 + 10

user93353

10/10/22, 4:13 AM

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

10/10/22, 4:21 AM

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?

SSA

10/10/22, 4:25 AM

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?

user93353

10/10/22, 4:31 AM

I can't think of any option at all :-) I am a noob.

user93353

10/10/22, 4:33 AM

`you have power of 2 is 8, for 3 is 2, etc` - what do you mean for 3 is 2?.

user93353

10/10/22, 4:35 AM

So 10! contains (2, 2^2, 2^3), (3, 3^2) & like this any factorial is made of prime powers - & hence this is a good way to find L - that's what you are saying, right?

SSA

10/10/22, 11:14 AM

yes, they are small odd primes, p-1 and q-1 are smooth integers. correcting in 10!, 3 has power of 4.

Samuel Neves

10/10/22, 9:51 PM

For the most part, the factorial isn't used for $p-1$. Or at least it shouldn't be. See my answer [here](https://crypto.stackexchange.com/a/72884/592).

user93353

10/14/22, 1:01 AM

@SamuelNeves - most books I have looked at seem to use Factorial rather than LCM. They don't even talk about LCM. For e.g. Silverman's Mathematical Cryptography, Smart's book, Joy of Factoring. The LCM method is mentioned in only a small fraction of the books. Any idea why this is so?

user93353

10/14/22, 1:32 AM

@SamuelNeves - another thing with Silverman's book is that he seems to be looking at B-smooth (p-1)s rather than B-powersmooth (p-1)s. And seems to imply that if p-1 is B-smooth then you need to go upto B!, whereas the LCM methods seem to say that if p-1 is B-powersmooth then you need to go upto LCM(1 to B). This is also a matter of confusion.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

TH: เหตุใดจึงใช้แฟกทอเรียลในอัลกอริทึม $p - 1$ ของ Pollard

RO: De ce este folosit factorial în algoritmul $p - 1$ al lui Pollard?

RU: Почему факториал используется в алгоритме Полларда $p - 1$?

VI: Tại sao giai thừa được sử dụng trong thuật toán $p - 1$ của Pollard?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.