From: cme@ellisun.sw.stratus.com (Carl Ellison)
Date: Mon, 11 Oct 93 08:19:49 PDT
To: cypherpunks@toad.com
Subject: Re:  Weak RSA keys?
Message-ID: <9310111518.AA01724@ellisun.sw.stratus.com>
MIME-Version: 1.0
Content-Type: text/plain


>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