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^{n-1} = 1 \pmod{n}\). This suggests the Fermat test for a prime: pick a random \(a \in \{1,...,n-1\}\) and see if \(a^{n-1} = 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

\[ \mathbb{Z}_{561} = \mathbb{Z}_{3} \times \mathbb{Z}_{11} \times \mathbb{Z}_{17} \]

thus each \(a \in \mathbb{Z}_{561}^*\) corresponds to some

\[ (x,y,z) \in \mathbb{Z}_{3}^* \times \mathbb{Z}_{11}^* \times \mathbb{Z}_{17}^* .\]

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 Miller-Rabin Test

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

\[ a^{n-1} = a^{2^s q}, a^{2^{s-1} q},...,a^q . \]

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.

When run on numbers of the form \(p q\) where \(p, q\) are large primes, the Miller-Rabin 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 Miller-Rabin test as follows:

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

  2. Pick a random \(a \in \{1,...,n-1\}\)

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

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

  5. Otherwise \(n\) is composite.

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

Ben Lynn 💡