> Date: Mon, 3 Aug 2015 04:04:01 +0000 > From: Viktor Dukhovni <openssl-us...@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. _______________________________________________ openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
