🚀 go-pugleaf

In article <9113@duke.duke.UUCP> srt@duke.UUCP (Stephen R. Tate) writes:

>I didn't see the earlier posting you refer to, but any test based on Lenstra's
>theorem is not ramdom, so any number of iterations above 1 is meaningless (and
>surely doesn't increase the "accuracy" of the test).
>
>The other interesting thing about Lenstra's theorem is that it *guarantee's*
>the result.  i.e., if it says a number is prime, then the number *is* prime --
>no possibility of error.

The earlier posting was a reference to the paper "A fast Monte-Carlo test
for primality" by R. Solovay and V. Strassen, SIAM Journal on Computing
(March 1977), 84-85.  Basicly, there's a test you can apply that's false
100% of the time for composite numbers and false < 50% of the time for
prime numbers.  If a number passes the test once, it has a better than
50% chance of being prime.  If you apply the test 100 times, and the number
passes every time, it has only a 1/2**100 chance of being composite.  You
can be as sure as you want that a number is prime, but you can never be
positive.  For practical purposes, this is sufficient for RSA.  The
advantage is that the algorithm is very fast.

See also: "Evaluation and Comparison of Two Efficient Probabilistic
Primality Testing Algorithms" by Louis Monier, Theoretical Computer
Science 12 (1980), 97-108.

		-ed falk, sun microsystems
		sun!falk, falk@sun.com
terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO.