Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Prime numbers and primality tests
Posted:
Jan 14, 2013 11:28 PM


A straightforward way to test a prime number candidate is the MillerRabin test (sometimes called the RabinMiller test). This well known and popular test is commonly executed 50 times on a candidate prime and has a proven probability of missing a nonprime of no more than 0.25 for each execution. Note that passing 50 MillerRabin tests (which is a de facto standard), the probability of nonprimality is 0.25^50 ~ 7.9*10^31, I'm satisfied that the number NextPrime gives me is "prime enough". Mathematica uses the MillerRabin test, although it is not clear how many iterations are used. As I understand it, Mathematica also the Lucas pseudo prime test on the MillerRabin output.
It is interesting to note, however, that the Lucas pseudo prime method of primality testing apparently does not have the handy "feature" of the MillerRabin test, namely, the provable, and bounded low probability of a wrong answer, from whence an estimate of primality for any number can be made without finding a counter example!
I've read that there are have been no counterexamples (viz., no nonprimes that pass the the Lucas pseudo prime test) to numbers that pass the Lucas pseudo prime test, but then again, I've never found an oyster with a pearl inside.
Is the MillerRabin a better test that the Lucas pseudo prime test?
http://reference.wolfram.com/mathematica/tutorial/IntegerAndNumberTheoreticalFunctions.html
http://reference.wolfram.com/mathematica/tutorial/SomeNotesOnInternalImplementation.html
http://mathworld.wolfram.com/LucasPseudoprime.html



