Primality Tests

By Fermat’s Theorem, if \(n\) is prime, then for any \(a\) we have \(a^{n-1} = 1 \pmod{n}\). This suggests the Fermat test for a prime: pick a random \(a \in [1..n-1]\) then see if \(a^{n-1} = 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)\).

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^{n-1} = 1\), then we also check \(a^{(n-1)/2} = \pm 1\), because \(a^{(n-1)/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 \(n-1\), that is, \(n-1 = 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 Miller-Rabin 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 Miller-Rabin 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 Miller-Rabin 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 Miller-Rabin 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 \(n-1 = 2^s q\) for some odd \(q\). Then we implement a single Miller-Rabin test as follows:

We also perform a few trial divisions by small primes before running the Miller-Rabin 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 polynomial-time algorithms for deciding primality (see Agrawal, Kayal and Saxena), though at present they are impractical.