From: hughes@ah.com (Eric Hughes)
Date: Tue, 12 Apr 94 10:15:07 PDT
To: cypherpunks@toad.com
Subject: more number theory
In-Reply-To: <199404120257.TAA26115@jobe.shell.portal.com>
Message-ID: <9404121704.AA21541@ah.com>
MIME-Version: 1.0
Content-Type: text/plain


>Failure depends on how many iterations
>you perform (n iterations = 2^-n chance of failure) and the values of
>the base you choose.

As I pointed out before, this probability is not correct.  The trials
are not independent, so you cannot just multiply them together.

>I'm familiar with two other primality testing algorithms [...]:
>Lucas' and Lehmer's.

For some good information on primality testing, see

	A Course in Computational Algebraic Number Theory
	by Henri Cohen

Chapter 9 is titled "Modern Primality Tests".  I give you fair warning
that you will not be able to understand this without significant
effort.  The Pocklington-Lehmer primality test is in Chapter 8
"Factoring in the Dark Ages".

There's a very interesting result stated here, "There exists a
probabilistic polynomial time algorithm which can prove or disprove
that a given number N is prime".  The result is by Adleman and Huang.
(Yes, _that_ Adleman.)

And for purposes of cultural literacy, the names are the Jacobi sum
test, the elliptic curve tests, Goldwasser-Kilian, and Atkin (a
development on G-K).

Eric