On Fri, Jul 31, 2015 at 12:35 PM, mancha <manc...@zoho.com> wrote: > If so, here's my quick & dirty back-of-envelope calculation (mod bound) > for the probability the gcd of two randomly chosen integers x,y is at > most k: > > k p(gcd(x,y)<=k) > - -------------- > 1 60.79% > 2 75.99% > 3 82.75% > 4 86.55% > 5 88.98% > 6 90.67% > 7 91.91% > 8 92.86% > 9 93.61% > 10 94.21% > > As can be seen, the probability is quite high the gcd will be small so > (p-1)(q-1) ~ lcm((p-1)(q-1)) removing the above benefit. > > But it's the end of the week and the neurons need respite so please let > me know if I'm missing something. >
You are correct, or at least very close. I was testing for GCD(p-1, q-1) == 4, when I should have been testing for GCD(p-1, q-1) == 2, since p-1 and q-1 are known to be even. Fixing that, I see that the probability of having GCD(p-1, q-1) == 2 for random odd numbers is a bit over 60% in the python runs. This will result most likely in a bit less a 2X runtime penalty for determining the primes. Bill
_______________________________________________ openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
