Number Theory

Given an integer $n$, how can we tell if $n$ is prime? The most obvious way is to look for factors of $n$, but no efficient factoring algorithm is known.

From now let us assume $n$ is odd, since deciding the primality of an even number is trivial.

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

Note if $a$ is not coprime to $n$ then the Fermat test fails. But if this happened often for large $n$, then we could easily recover a factor by computing $\gcd (a,n)$ and we have have an efficient factoring algorithm!

We can improve things by using the fact that there are no nontrival square roots of unity modulo a prime.

One promising idea is to first check $a^{n-1}=1$, then check that $a^{(n-1)/2}=\pm 1$, because $a^{(n-1)/2}$ is a square root of 1.

Unfortunately, this is still not sufficient, for example the third Carmichael number $1729$ still passes. To defeat numbers like this, we iterate this idea as follows.

Let $2^s$ be the largest power of 2 dividing $n-1$, thus we have $n-1=2^{s}q$ for some odd number $q$. Consider the sequence

$$a^{n-1}=a^{2^{s}q},a^{2^{s-1}q},...,a^q.$$

We have set this sequence up so that each member of the sequence is a square root of the preceding member.

Then if $n$ is prime, by Fermat's theorem this sequence must start with 1. Also from our notes on polynomials, when $n$ is prime, the only square roots of $1(modn)$ are $\pm 1$. Hence either every element of the sequence is 1, or the first member of the sequence not equal to $1$ must be $-1$.

The Miller-Rabin test works by picking a random $a\in {\mathbb{Z}}_n$ then checking that the above sequence has the correct form. If the 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 that 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$. Again from our work on polynomials, this means we can factor $n$.

When run on numbers of the form $pq$ where $p,q$ are random primes of a certain size, the Miller-Rabin test fails almost always because the sequence does not start with 1. Thus we cannot break RSA in this fashion. However, note that Carmichael numbers are always easy to factor since the sequence proving the compositeness starts with 1.

In practice, we implement the Miller-Rabin test as follows:

Given $n$, pick a random $a\in \{1,...,n-1\}$ and find $s$ so that $n-1=2^{s}q$ for some odd $q$. If $a^q=1$ then $n$ passes (and exit). For $i=0,...,s-1$ see if $a^{2^{i}q}=-1$. If so, $n$ passes (and exit). Otherwise $n$ is composite.

Also one usually performs 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. They only ever prove that an input is composite.

There exist deterministic polynomial-time algorithms for deciding whether a number is prime or not (see Agrawal, Kayal and Saxena), though at present they are impractical as probabilistic tests are much faster.