From: hughes@ah.com (Eric Hughes)
Date: Tue, 12 Apr 94 09:54:45 PDT
To: cypherpunks@toad.com
Subject: number theory
In-Reply-To: <199404112227.PAA07925@mail2.netcom.com>
Message-ID: <9404121644.AA21493@ah.com>
MIME-Version: 1.0
Content-Type: text/plain


>If a^(n-1) mod n != 1, the number is composite and can be
>rejected.  But, if a^(n-1) mod n == 1, you can only be 50% sure n is
>prime.  

I should point out that the standard argument that picking 'k'
different values for 'a' and then calculating the probability as
(1/2)^k is fallacious.  This would be true if the probabilities were
independent, but they aren't.  There was a paper on this about five
years ago whose awareness has not been yet widespread.  I no longer
have the reference.

For everybody that wants to really know about this, find out about the
Miller-Rabin test.

>(Roughly speaking; Phil Karn notes that the PGP docs indicate
>a 50%, I've seen proofs that this pseudoprime test fails 50% of the
>time, etc.  But these are upper bounds; the real percentage seems much
>lower and I haven't seen a tighter bound on it).

The 50% figure is easy to show with some considerations about
quadratic residues.  Tightening the bound is much more difficult.

Eric