Primality Tests
Given an integer \(n\), how can we tell if \(n\) is prime? Assume \(n\) is odd, since the even case is trivial.
The most obvious idea is to look for factors of \(n\), but no efficient factoring algorithm is known.
The Fermat Test
By Fermat’s Theorem, if \(n\) is prime, then for any \(a\) we have \(a^{n1} = 1 \pmod{n}\). This suggests the Fermat test for a prime: pick a random \(a \in [1..n1]\) then see if \(a^{n1} = 1 \pmod{n}\). If not, then \(n\) must be composite.
However, equality may hold even when \(n\) is not prime. For example, take \(n = 561 = 3\times 11\times 17\). By the Chinese Remainder Theorem
thus each \(a \in \mathbb{Z}_{561}^*\) corresponds to some
By Fermat’s Theorem, \(x^2 = 1\), \(y^{10} = 1\), and \(z^{16} = 1\). Since 2, 10, and 16 all divide 560, this means \((x,y,z)^{560} = (1,1,1)\), in other words, \(a^{560} = 1\) for any \(a \in \mathbb{Z}_{561}^*\).
Thus no matter what \(a\) we pick, \(561\) always passes the Fermat test despite being composite so long as \(a\) is coprime to \(n\). Such numbers are called Carmichael numbers, and it turns out there are infinitely many of them.
If \(a\) is not coprime to \(n\) then the Fermat test fails, but in this case we can recover a factor of \(n\) by computing \(\gcd(a, n)\).
The MillerRabin Test
We can do better by recalling \(n\) is prime if and only if the solutions of \(x^2 = 1 \pmod{n}\) are \(x = \pm 1\).
So if \(n\) passes the Fermat test, that is, \(a^{n1} = 1\), then we also check \(a^{(n1)/2} = \pm 1\), because \(a^{(n1)/2}\) is a square root of 1.
Unfortunately, numbers such as the third Carmichael number \(1729\) still fool this enhanced test. But what if we iterate? That is, so long as it’s possible, we continue halving the exponent until we reach a number besides 1. If it’s anything but \(1\) then \(n\) must be composite.
More formally, let \(2^s\) be the largest power of 2 dividing \(n1\), that is, \(n1 = 2^s q\) for some odd number \(q\). Each member of the sequence
is a square root of the preceding member.
Then if \(n\) is prime, this sequence begins with 1 and either every member is 1, or the first member of the sequence not equal to \(1\) is \(1\).
The MillerRabin test picks a random \(a\in\mathbb{Z}_n\). If the above sequence does not begin with \(1\), or the first member of the sequence that is not \(1\) is also not \(1\) then \(n\) is not prime.
It turns out for any composite \(n\), including Carmichael numbers, the probability \(n\) passes the MillerRabin test is at most \(1/4\). (On average it is significantly less.) Thus the probability \(n\) passes several runs decreases exponentially.
If \(n\) fails the MillerRabin test with a sequence starting with 1, then we have a nontrivial square root of \(1\) modulo \(n\), and we can efficiently factor \(n\). Thus Carmichael numbers are always easy to factor.
Exercise: What happens when we run the MillerRabin test on numbers of the form \(p q\) where \(p, q\) are large primes? Can we break RSA with it?
Given \(n\), find \(s\) so that \(n1 = 2^s q\) for some odd \(q\). Then we implement a single MillerRabin test as follows:

Pick a random \(a \in [1..n1]\).

If \(a^q = 1\) then \(n\) passes.

Otherwise, for \(i = 0,...,s1\) see if \(a^{{2^i} q} = 1\). If so, \(n\) passes.

Otherwise \(n\) is composite.
We also perform a few trial divisions by small primes before running the MillerRabin test several times.
Strictly speaking, these tests are compositeness tests since they do not prove the input is prime, but rather prove that an input is composite.
There exist deterministic polynomialtime algorithms for deciding primality (see Agrawal, Kayal and Saxena), though at present they are impractical.