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

[Viktor Dukhovni]

On Sun, Aug 02, 2015 at 08:08:52PM -0600, Hilarie Orman wrote:

> For primes p and q for which p-1 and q-1 have no common factor <= n,

Other than 2 of course.

> probability of gcd(p, q) > 1 is very roughly 1/n.

That would be gcd(p-1, q-1), since gcd(p,q) is of course 1,
unless p == q.

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

That's expensive to do.

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

This is much cheaper, but why (p^2-1, q^2-1), rather than just
(p-1, q-1).  What use is a common factor (other than 2) of (p+1,
q-1) or (p+1, q+1)?

-- 
	Viktor.