4 ms·

https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes#Cryptography https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes... says: > with the curr

• 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.