🚀 go-pugleaf

In article <12417@sun.uucp> falk@sun.UUCP (Ed Falk) writes:
>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

Ah, but this has nothing to do with Lenstra's theorem.  This test is
called the Solovay Strassen test (clever, huh?).  I never understood
why people use this test any more.  A paper that was written quite a
while back (by Rabin, I think) showed that the Strong Pseudoprime Test
has the same running time as SS, and gave the correct answer every time
that SS did.  In fact, not only is the "correct answer set" of Solovay-
Strassen a subset of the Strong Pseudoprime Test, but you can prove
that the Strong Pseudoprime test has a probability of error of only 1/4,
instead of 1/2.  Therefore, only half as many tests are needed. (And no
non-obvious rules like those for computing Jacobi symbols need to be used).

-- 
Steve Tate			UUCP: ..!{ihnp4,decvax}!duke!srt
				CSNET: srt@duke
				ARPA:  srt%duke@csnet-relay