The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm 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 <math>n>2</math>, let’s write <math>n-1</math> as <math>2^sd</math> where <math>s</math> is a positive integer and <math>d</math> is an odd positive integer. Let’s consider an integer <math>a</math>, called a base, which is coprime to <math>n</math>.

Then, <math>n</math> is said to be a strong probable prime to base a if one of these congruence relations holds:

  • <math>a^d \equiv 1 \!\!\!\pmod n</math>, or
  • <math>a^{2^r d} \equiv -1 \!\!\!\pmod n</math> for some <math>0

\leq r<s</math>.

This simplifies to first checking for <math>a^d \equiv 1 \pmod{n}</math> and then <math>a^{2^r d} \equiv n-1 \pmod{n} </math> for successive values of <math>r</math>. For each value of <math>r</math>, the value of the expression may be calculated using the value obtained for the previous value of <math>r</math> by squaring under the modulus of <math>n</math>.

The idea beneath this test is that when <math>n</math> is an odd prime, it passes the test because of two facts:

  • by Fermat's little theorem, <math>a^{n-1} \equiv 1 \pmod{n}</math> (this property alone defines the weaker notion of probable prime to base <math>a</math>, on which the Fermat test is based);
  • the only square roots of 1 modulo <math>n</math> are 1 and −1.

Hence, by contraposition, if <math>n</math> is not a strong probable prime to base <math>a</math>, then <math>n</math> is definitely composite, and <math>a</math> is called a witness for the compositeness of <math>n</math>.

However, this property is not an exact characterization of prime numbers. If <math>n</math> is composite, it may nonetheless be a strong probable prime to base <math>a</math>, in which case it is called a strong pseudoprime, and <math>a</math> is a strong liar.

Choices of bases

No composite number is a strong pseudoprime to all bases at the same time (contrary to the Fermat primality test for which Fermat pseudoprimes to all bases exist: the Carmichael numbers). However no simple way of finding a witness is known. A naïve solution is to try all possible bases, which yields an inefficient deterministic algorithm. The Miller test is a more efficient variant of this (see section Miller test below).

Another solution is to pick a base at random. This yields a fast probabilistic test. When n is composite, most bases are witnesses, so the test will detect n as composite with a reasonably high probability (see section Accuracy below). We can quickly reduce the probability of a false positive to an arbitrarily small rate, by combining the outcome of as many independently chosen bases as necessary to achieve the said rate. This is the Miller–Rabin test. There seems to be diminishing returns in trying many bases, because if n is a pseudoprime to some base, then it seems more likely to be a pseudoprime to another base.

Note that holds trivially for , because the congruence relation is compatible with exponentiation. And holds trivially for since is odd, for the same reason. That is why random are usually chosen in the interval .

For testing arbitrarily large , choosing bases at random is essential, as we don't know the distribution of witnesses and strong liars among the numbers 2, 3, ..., .

However, a pre-selected set of a few small bases guarantees the identification of all composites up to a pre-computed maximum. This maximum is generally quite large compared to the bases. This gives very fast deterministic tests for small enough n (see section Testing against small sets of bases below).

Proofs

Here is a proof that, if n is a prime, then the only square roots of 1 modulo n are 1 and −1.

Here is a proof that, if n is an odd prime, then it is a strong probable prime to base a.

Example

Suppose we wish to determine if <math>n = 221</math> is prime. We write <math>n - 1 \text{ as } 2^2 \times 55</math>, so that we have <math>s = 2 \text{ and } d = 55</math>. We randomly select a number <math>a</math> such that <math>2 \leq a \leq n-2</math>.

Say <math>a = 174</math>:

<math>

\begin{align}

a^