[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Weak RSA keys?

>Date: Thu, 7 Oct 93 14:35:52 -0700
>From: [email protected] (Eric Hughes)
>Message-Id: <[email protected]>

>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