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 n > 2 {\displaystyle n>2} , let’s write n − 1 {\displaystyle n-1} as 2 s d {\displaystyle 2^{s}d} where s {\displaystyle s} is a positive integer and d {\displaystyle d} is an odd positive integer. Let’s consider an integer a {\displaystyle a} , called a base, which is coprime to n {\displaystyle n} . Then, n {\displaystyle n} is said to be a strong probable prime to base a if one of these congruence relations holds:
a d ≡ 1 ( mod n ) {\displaystyle a^{d}\equiv 1\!\!\!{\pmod {n}}} , or
a 2 r d ≡ − 1 ( mod n ) {\displaystyle a^{2^{r}d}\equiv -1\!\!\!{\pmod {n}}} for some 0 ≤ r < s {\displaystyle 0\leq r<s} . This simplifies to first checking for a d ≡ 1 ( mod n ) {\displaystyle a^{d}\equiv 1{\pmod {n}}} and then a 2 r d ≡ n − 1 ( mod n ) {\displaystyle a^{2^{r}d}\equiv n-1{\pmod {n}}} for successive values of r {\displaystyle r} . For each value of r {\displaystyle r} , the value of the expression may be calculated using the value obtained for the previous value of r {\displaystyle r} by squaring under the modulus of n {\displaystyle n} . The idea beneath this test is that when n {\displaystyle n} is an odd prime, it passes the test because of two facts:
by Fermat's little theorem, a n − 1 ≡ 1 ( mod n ) {\displaystyle a^{n-1}\equiv 1{\pmod {n}}} (this property alone defines the weaker notion of probable prime to base a {\displaystyle a} , on which the Fermat test is based); the only square roots of 1 modulo n {\displaystyle n} are 1 and −1. Hence, by contraposition, if n {\displaystyle n} is not a strong probable prime to base a {\displaystyle a} , then n {\displaystyle n} is definitely composite, and a {\displaystyle a} is called a witness for the compositeness of n {\displaystyle n} . However, this property is not an exact characterization of prime numbers. If n {\displaystyle n} is composite, it may nonetheless be a strong probable prime to base a {\displaystyle a} , in which case it is called a strong pseudoprime, and a {\displaystyle a} is a strong liar.
… excerpt ends here. Continue reading the full article.
