Weak RSA keys?

[Carl Ellison]

>Date: Thu, 7 Oct 93 14:35:52 -0700
>From: hughes at ah.com (Eric Hughes)
>Message-Id: <9310072135.AA01702 at 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