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

[Hilarie Orman]

>  Date: Mon, 3 Aug 2015 04:04:01 +0000
>  From: Viktor Dukhovni <openssl-users at dukhovni.org>

>  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.
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.
Thank you.  Yes, of course.

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

Twice as expensive.  Is that really expensive?

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

Rules out Lucas sequences. 

>  -- 
>	   Viktor.