A primality test that provides an efficient probabilistic algorithm for determining if a given number is prime. It is based on the properties of strong pseudoprimes.
The algorithm proceeds as follows. 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 
. If 
multiple independent tests are performed on a composite
number, then the probability that it passes each test is 
or less.
However, if the smallest composite number that passes a particular set of tests is known ahead of time, then that set of tests constitutes a primality proof
for all smaller numbers. The sequence of smallest odd numbers passing a multiple
Rabin-Miller test using the first 
primes for 
, 2, ... is given by 2047, 1373653, 25326001, 3215031751,
2152302898747, 3474749660383, 341550071728321, 341550071728321, ... (OEIS A014233;
Jaeschke 1993). Therefore, multiple Rabin tests using the first 7 primes (using 8
gives no improvement) are valid for every number up to 
.
The Wolfram Language implements the multiple Rabin-Miller test in bases 2 and 3 combined with a Lucas
pseudoprime test as the primality test used
by the function PrimeQ[n].
As of 1997, this procedure is known to be correct only for all 
, but no counterexamples are known and if any exist,
they are expected to occur with extremely small probability (i.e., much less than
the probability of a hardware error on a computer performing the test).
." Math. Comput. 35, 1003-1026,
1980.