The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic
primality test: an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
which determines whether a given number is
likely to be prime, similar to the
Fermat primality test and the
Solovay–Strassen primality test.
It is of historical significance in the search for a
polynomial-time deterministic primality test. Its probabilistic variant remains widely used in practice, as one of the simplest and fastest tests known.
Gary L. Miller discovered the test in 1976. Miller's version of the test is
deterministic, but its correctness relies on the unproven
extended Riemann hypothesis.
Michael O. Rabin modified it to obtain an unconditional
probabilistic algorithm in 1980.
Mathematical concepts
Similarly to the Fermat and Solovay–Strassen tests, the Miller–Rabin primality test checks whether a specific property, which is known to hold for prime values, holds for the number under testing.
Strong probable primes
The property is the following. For a given odd integer
, let’s write
as
where
is a positive integer and
is an odd positive integer. Let’s consider an integer
, called a ''base'', which is
coprime
In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equiv ...
to
.
Then,
is said to be a strong
probable prime to base ''a'' if one of these
congruence relations holds:
*
, or
*
for some