<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Jul 31, 2015 at 12:35 PM, mancha <span dir="ltr"><<a href="mailto:mancha1@zoho.com" target="_blank">mancha1@zoho.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">If so, here's my quick & dirty back-of-envelope calculation (mod bound)<br>
for the probability the gcd of two randomly chosen integers x,y is at<br>
most k:<br>
<br>
k       p(gcd(x,y)<=k)<br>
-       --------------<br>
1       60.79%<br>
2       75.99%<br>
3       82.75%<br>
4       86.55%<br>
5       88.98%<br>
6       90.67%<br>
7       91.91%<br>
8       92.86%<br>
9       93.61%<br>
10      94.21%<br>
<br>
As can be seen, the probability is quite high the gcd will be small so<br>
(p-1)(q-1) ~ lcm((p-1)(q-1)) removing the above benefit.<br>
<br>
But it's the end of the week and the neurons need respite so please let<br>
me know if I'm missing something.<br></blockquote><div><br></div><div>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.</div><div><br></div><div>Bill </div></div></div></div>