From: cme@ellisun.sw.stratus.com (Carl Ellison)
Date: Mon, 11 Oct 93 08:51:32 PDT
To: cypherpunks@toad.com
Subject: E[gcd(p-1,q-1)]
Message-ID: <9310111549.AA01795@ellisun.sw.stratus.com>
MIME-Version: 1.0
Content-Type: text/plain


I just wrote:
>
>	E = sum_i sum_m p_i^{-m}
>
>where p_i is the i-th prime.

That didn't take into account that p and q were knwn to be odd.   So,
assuming p and q are randomly chosen odd numbers:

	E[gcd(p-1,q-1)] < 2.5 + sum_j 1/(p_j - 1)

where p_j is the j-th odd prime.

It's "<" because this doesn't take into account that there are (relatively
small) values of m such that p_i^m > min(p,q).  It also doesn't take into
account the second order probability effects from depeltion of range.

 - Carl