17 Dec
2003
17 Dec
'03
11:17 p.m.
Date: Thu, 7 Oct 93 14:35:52 -0700 From: hughes@ah.com (Eric Hughes) Message-Id: <9310072135.AA01702@ah.com>
Out of curiosity, does anybody here know how to calculate any expectations for gcd(p-1,q-1) for, say, 2^n < p < q < 2^(n+1) ? I don't know enough number theory myself.
Eric, I don't think it's number theory you want so much as probability theory. I'm going to look at this to get the answer to the problem as you formulated it, but for values of n large enough (or, for values of 0 greater than (2^{-n}) :-) there's a simple form for that expected value. You can take it as an upper bound for the actual one: [note: I haven't verified this more than once...] E = sum_i sum_m p_i^{-m} where p_i is the i-th prime. - Carl