1993-10-11 - E[gcd(p-1,q-1)]

Header Data

From: cme@ellisun.sw.stratus.com (Carl Ellison)
To: cypherpunks@toad.com
Message Hash: ae9582b0dfa11ff3e85147fe075a236e2f4a30b60582f8ffde0c2c54d41f031e
Message ID: <9310111549.AA01795@ellisun.sw.stratus.com>
Reply To: N/A
UTC Datetime: 1993-10-11 15:51:32 UTC
Raw Date: Mon, 11 Oct 93 08:51:32 PDT

Raw message

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