more number theory

[hughes@ah.com (Eric Hughes)]

>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