number theory

[hughes@ah.com (Eric Hughes)]

>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