The Rabin-Miller strong pseudoprime test is a probabilistic primality test based on the properties of strong pseudoprimes. It efficiently detects composite numbers, while an odd prime number always passes.
The algorithm proceeds as follows. Given an odd integer 
, let 
, where 
is a positive integer
and 
is odd. Then choose an integer 
uniformly at random with 
. If 
or 
for some integer 
satisfying 
, then 
passes the test. A prime will
pass the test for all 
. If neither condition holds, 
is a composite number.
The test requires 
modular multiplications
per base, where 
is the logarithm base 2. A
number which passes the test is not necessarily a prime
number. Monier (1980) and Rabin (1980) showed that an odd composite number passes the test for at most 1/4
of the possible bases 
. For a fixed composite number,
independent uniform choices of 
therefore have probability
at most 
of all passing, where 
is a positive integer.
If the smallest composite number passing a fixed set of bases is known, those bases give a deterministic primality
test below that bound, with candidates equal to a prime
number used as a base accepted separately. The sequence
of smallest odd composite
numbers passing a multiple Rabin-Miller test using the first 
primes for 
, 2, ... is 2047, 1373653, 25326001, 3215031751, 2152302898747,
3474749660383, 341550071728321, 341550071728321, ... (OEIS A014233;
Jaeschke 1993). Thus the bases 2, 3, 5, 7, 11, 13, and 17 suffice below 
. Adding base 19 does not increase this bound.
The probability bound 
applies to independent uniformly random bases and does
not apply to a fixed list of bases.
The documented Wolfram Language implementation of PrimeQ[n] first checks divisibility by small primes, then applies this test in bases 2 and 3 and a Lucas pseudoprime test. No composite number is known to pass this combined procedure. Its correctness for all positive integers is unproved.
."
Math. Comput. 35, 1003-1026, 1980. 