# Miller-Rabin Primality Test

Fermat's little theorem states that for a prime number $p$, any $a\in \Z/p^\times$ satisfies $a^{p-1} = 1$. If $p$ is not prime, this may not necessarily be true. For example:
$$2^{402} = 376 \in \Z/403^\times.$$ Therefore, we can conclude that 403 is not a prime number. In fact, $403 = 13\cdot 31$ Fermat's little theorem can be used as a test for compositeness this way: if you can find a number $a$ relatively prime to $p$ such that $a^{p-1} \not\equiv 1\pmod{p}$, then $p$ is actually composite.

If there exists an $a\in\{1,\dots,p-1\}$ with $a^{p-1}\not\equiv 1\pmod{p}$, then $a$ is called a Fermat witness to the compositeness of $p$. That is, it proves that $p$ is composite. Notice that we do not require $a$ to be relatively prime to $p$ in this definition of a Fermat witness: if any number $a\lt p$ exists with $a^{p-1}\not\equiv 1\pmod{p}$, then $p$ cannot be prime, because if it were, $a$ would actually be relatively prime to $p$ and this would contradict Fermat's little theorem.

Fermat's little theorem is a pretty good test for compositeness: if $p$ is some odd composite integer with at least one relatively prime Fermat witness, then at least half the numbers in the range $2,3,\dots,p-2$ will also be witnesses. Note: we are using this range because $p-1$ and $1$ aren't witnesses. Therefore, you can use Fermat's little theorem as a randomized prime-testing algorithm: randomly select elements $a$ from $\{2,\dots,p-2\}$ and check if they satisfy $a^{p-1} = 1\pmod{p}$. Therefore, if you have some large number $N$ that is composite and has at least one witness, a randomised Fermat's little theorem algorithm randomly testing $K$ different bases in $\{2,\dots,N-1\}$ will have probability of less than $1/2^K$ at failing to detect that $N$ is composite.

## Enter Carmichael

The catch is that $N$ needs at least one witness for the probability estimation at $1/2$ per attempt. Not all numbers have at least one relatively prime witness. These are called Carmichael numbers. In other words, a Carmichael number is a number $N$ such that $a^{N-1} \equiv 1\pmod{N}$ for all integers $a$ relatively prime to $N$. An example is
$$561 = 3\cdot 11\cdot 17.$$ Notice that $17^{560}\equiv 34\pmod{561}$, which still proves that $561$ is composite (remember: if 561 were prime then 17 would be relatively prime to 561). But the bad thing is that the Fermat little theorem-test no longer will give at least a 1/2 probability of showing that a Carmichael number is composite on a randomly chosen base. For Carmichael numbers, there are very few witnesses, and there are infinitely many Carmichael numbers.

## Enhancing Fermat

There is a souped-up version of the Fermat little theorem-test called the Miller-Rabin test that works well even for Carmichael numbers. It's based upon the following observation:

Theorem. Let $p$ be an odd prime and write $p-1=2^kq$ where $q$ is an odd number. If $a$ is relatively prime to $p$ then at least one of the following is true:

1. $a^q\equiv 1\pmod{p}$, or
2. At least one of $a^q, a^{2q},\dots,a^{2^{k-1}q}$ is congruent to $-1$ modulo $p$
Proof. Fermat's little theorem states that $a^{2^kq} = a^{p-1}\equiv 1\pmod{p}$. This number is obtained by starting out with $a^q$ and repeatedly squaring it. Therefore, if the first statement does not hold, at least one number in the list $a^q, (a^q)^2 = a^{2q},\dots$ must be a number that squares to give $1$ and is not $1$, and hence must be $-1$.

So, we call a number $a\in \{1,\dots,p-1\}$ a Miller-Rabin witness if it satisfies neither of the conditions of the theorem. A Miller-Rabin witness is much like a regular ol' Fermat witness, but it's a little better in that a randomised algorithm choosing bases $a\in \{2,\dots,p-2\}$ will have only a 1/4 chance of failing for each base for any composite number $p\geq 3$. So, while a little more computation is required for each base, the Miller-Rabin test can weed out all composite numbers, even the Carmichael ones.