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\}\) and see if \(a^{n1} = 1 \pmod{n}\). If not, then \(n\) must be composite.
However we may still get equality 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 then we can easily 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.
When run on numbers of the form \(p q\) where \(p, q\) are large primes, the MillerRabin test fails almost always because the sequence does not start with 1. Thus we cannot break RSA in this fashion.
In practice, we implement the MillerRabin test as follows:

Given \(n\), find \(s\) so that \(n1 = 2^s q\) for some odd \(q\).

Pick a random \(a \in \{1,...,n1\}\)

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

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

Otherwise \(n\) is composite.
We also perform a few trial divisions by small primes before running the MillerRabin test.
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.