Rabin-Miller Strong Pseudoprime Test

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 $n$, let $n=2^rs+1$ with $s$ Odd. Then choose a random integer $a$ with $1\leq a\leq n-1$. If $a^s\equiv 1\ \left({{\rm mod\ } {n}}\right)$ or $a^{2^j s}\equiv -1\ \left({{\rm mod\ } {n}}\right)$ for some $0\leq j\leq r-1$, then $n$ passes the test. A Prime will pass the test for all $a$.

The test is very fast and requires no more than $(1+{\it o}(1))\lg n$ multiplications (mod $n$), 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 $a$.

The Rabin-Miller test (combined with a Lucas Pseudoprime test) is the Primality Test used by Mathematica ${}^{\scriptstyle\circledRsymbol}$ versions 2.2 and later (Wolfram Research, Champaign, IL). As of 1991, the combined test had been proven correct for all $n<2.5\times 10^{10}$, 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 $3.4\times 10^{14}$.

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.