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.
_______________________________________________
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
