3 ms·

> you want each of p-1 and q-1 to have large factors Why?

by jwilk 5y ago

ColinWright 5y ago
At it's simplest, the algebraic structure of the integers modulo (pq) is simpler when p-1 or q-1 are "smooth" (have no big factors for some definition of "big") and that means that algebraic methods of factoring can be more effective. It's a complicated topic. The magic terms to search for are "strong prime" or "Sophie Germain Prime". Disclaimer: I'm not an expert ... someone else might be able to comment more usefully.
- jwilk 5y ago
  https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes#Cryptography https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes... says: > with the current factorization technology, the advantage of using safe and strong primes appears to be negligible (I'm not an expert either.)
  - ColinWright 5y ago
    With a quick skim by my non-expert eye, they are really saying that using the full limit of "strong primes" is unnecessary, and that it suffices to use random primes. But random primes are not such that p-1 is smooth, "random primes" will still have a reasonably large factor, so the comment remains. If you take it to an extreme, using a prime p of the form 2^k+1 makes pq reasonably easy to factor (I think) using the Pollard P-1 algorithm. So there's still value in ensuring that p-1 and q-1 both have a reasonably large factor. But I'm at, and possibly beyond, my actual knowledge, and somewhat into "better safe than sorry" speculation.
  - ColinWright 5y ago
    While doing other rsearch I stumbled across this quotation from Wikipedia: > The numbers p and q should not be "too close", lest the Fermat factorization for n be successful. If p − q is less than 2n^{1/4} (n = p⋅q, which even for "small" 1024-bit values of n is 3×10^{77}), solving for p and q is trivial. Furthermore, if either p − 1 or q − 1 has only small prime factors, n can be factored quickly by Pollard's p − 1 algorithm, and hence such values of p or q should be discarded. Wikipedia is not always right, and certainly shouldn't be trusted implicitly on details in depth, but it's an interesting thing for them to be saying.

> you want each of p-1 and q-1 to have large factors Why?

by jwilk 5y ago

> you want each of p-1 and q-1 to have large factors Why?

At it's simplest, the algebraic structure of the integers modulo (pq) is simpler when p-1 or q-1 are "smooth" (have no big factors for some definition of "big") and that means that algebraic methods of factoring can be more effective. It's a complicated topic. The magic terms to search for are "strong prime" or "Sophie Germain Prime". Disclaimer: I'm not an expert ... someone else might be able to comment more usefully.

jwilk 5y ago
https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes#Cryptography https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes... says: > with the current factorization technology, the advantage of using safe and strong primes appears to be negligible (I'm not an expert either.)
- ColinWright 5y ago
  With a quick skim by my non-expert eye, they are really saying that using the full limit of "strong primes" is unnecessary, and that it suffices to use random primes. But random primes are not such that p-1 is smooth, "random primes" will still have a reasonably large factor, so the comment remains. If you take it to an extreme, using a prime p of the form 2^k+1 makes pq reasonably easy to factor (I think) using the Pollard P-1 algorithm. So there's still value in ensuring that p-1 and q-1 both have a reasonably large factor. But I'm at, and possibly beyond, my actual knowledge, and somewhat into "better safe than sorry" speculation.
- ColinWright 5y ago
  While doing other rsearch I stumbled across this quotation from Wikipedia: > The numbers p and q should not be "too close", lest the Fermat factorization for n be successful. If p − q is less than 2n^{1/4} (n = p⋅q, which even for "small" 1024-bit values of n is 3×10^{77}), solving for p and q is trivial. Furthermore, if either p − 1 or q − 1 has only small prime factors, n can be factored quickly by Pollard's p − 1 algorithm, and hence such values of p or q should be discarded. Wikipedia is not always right, and certainly shouldn't be trusted implicitly on details in depth, but it's an interesting thing for them to be saying.