From: Anonymous <mg5n+ea1e6llvoz70pb6bweqlrmyla4udd80xgn0a0saq03@andrew.cmu.edu>
Date: Tue, 12 Apr 94 17:12:23 PDT
To: mg5n+anz3ajg8o1yxicqzt6v6qgpg3tkhddpqw3jl@andrew.cmu.edu (cypherpunks)
Subject: Yet more number theory
Message-ID: <Added.whenXMS00UddMbm05=@andrew.cmu.edu>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

Well, I'm the person posting all the number theory stuff anonymously.
Well, not too anonymously since I am signing each post... ;)

I thought I'd try out Matt Ghio's service.  I'm not sure exactly what
will happen, but hopefully you will able to reply to this message and
reach me!

Anyway, I got my copy of "Elementary Number Theory and its
Applications" by Kenneth Rosen just now, and checked Miller-Rabin
primality testing, and pseudoprime primality testing.  Eric pointed
out some recent work (by Pomerance I presume) and it does indeed junk
the notion that for pseudoprime testing, the failure rate is 2^-n, n
being the number of trials.

However, Miller-Rabin isn't susceptible (it uses strong pseudoprime
testing) - and what it even better is the latest bound is 4^-k!  That
is, if you pick k integers and perform M-R on n for each, the chance a
composite will pass is less than (1/4)^k.

And, there is no analogy of a Carmichael number for strong
pseudoprimes.

So I guess the bottom line is M-R is the way to go.


-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLas39YOA7OpLWtYzAQETVQP/YzHMudKp/ehgcG0MkBeoyhQsItAlAvXL
VVj2VN2ac7KjlqtyP/Frjq+6s/T0ai4MhojboaWKBJfuUvZT1hBj0c0PvkaHVeiQ
H1eJpEXEqbFoouRX/M7ZYLmwfeJenKn0th408gJBf6yDHwdv9dyo7//Hhd/GreWJ
K+9nHl4k3kU=
=9zRl
-----END PGP SIGNATURE-----