E[gcd(p-1,q-1)]

Carl Ellison cme at ellisun.sw.stratus.com
Mon Oct 11 08:51:32 PDT 1993


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







More information about the cypherpunks-legacy mailing list