[openssl-dev] common factors in (p-1) and (q-1)

[Hilarie Orman]

For primes p and q for which p-1 and q-1 have no common factor <= n,
probability of gcd(p, q) > 1 is very roughly 1/n.

Therefore,
1.  Use strong primes as in Rivest/Silverman.  Simply described,
choose large primes r and s.  Choose small factors i and j, gcd(i, j)
= 1.  Find p such that 1+2*i*r is prime and q such that 1+2*j*s is
prime.

Or

2.  Find large primes p and q such that gcd(p^2-1, q^2-1) < 10^6.

Hilarie