A Primality Test which provides an efficient probabilistic Algorithm for determining if a given number is Prime. It is based on the properties of Strong Pseudoprimes. Given an Odd Integer , let with Odd. Then choose a random integer with . If or for some , then passes the test. A Prime will pass the test for all .
The test is very fast and requires no more than multiplications (mod ), where Lg is the Logarithm base 2. Unfortunately, a number which passes the test is not necessarily Prime. Monier (1980) and Rabin (1980) have shown that a Composite Number passes the test for at most 1/4 of the possible bases .
The Rabin-Miller test (combined with a Lucas Pseudoprime test) is the Primality Test used by Mathematica versions 2.2 and later (Wolfram Research, Champaign, IL). As of 1991, the combined test had been proven correct for all , but not beyond. The test potentially could therefore incorrectly identify a large Composite Number as Prime (but not vice versa). Strong Pseudoprime tests have been subsequently proved valid for every number up to .
See also Lucas-Lehmer Test, Miller's Primality Test, Pseudoprime, Strong Pseudoprime
References
Arnault, F. ``Rabin-Miller Primality Test: Composite Numbers Which Pass It.'' Math. Comput. 64, 355-361, 1995.
Miller, G. ``Riemann's Hypothesis and Tests for Primality.'' J. Comp. Syst. Sci. 13, 300-317, 1976.
Monier, L. ``Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms.''
Theor. Comput. Sci. 12, 97-108, 1980.
Rabin, M. O. ``Probabilistic Algorithm for Testing Primality.'' J. Number Th. 12, 128-138, 1980.
Wagon, S. Mathematica in Action. New York: W. H. Freeman, pp. 15-17, 1991.
© 1996-9 Eric W. Weisstein