# 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 blynn@cs.stanford.edu 💡