18 Fermat and Miller-Rabin Primality Tests

Lecture from: 17.04.2025 | Video: Homelab

Motivation for Advanced Primality Tests

Simple approaches to primality testing, such as checking for small divisors or relying on basic properties like $\gcd (a,n)=1$ for randomly chosen $a$, can be unreliable.

For instance, a test declaring $n$ prime if a randomly chosen $a\in \{1,\dots ,n-1\}$ satisfies $\gcd (a,n)=1$, and composite otherwise, has a significant error probability for composite numbers.

The probability of incorrectly declaring a composite $n$ as prime (i.e., choosing an $a$ such that $\gcd (a,n)=1$) is $\frac{\varphi (n)}{n-1}$. For certain composite numbers, this value can be very close to 1. Consider $n=p^2$ for a prime $p$; here, $\varphi (n)=p(p-1)$, and the error probability becomes $\frac{p(p-1)}{p^2-1}=\frac{p}{p+1}$, which approaches 1 for large $p$.

This high error rate necessitates more sophisticated methods, leading us to tests based on Fermat’s Little Theorem and related group-theoretic principles.

The Fermat Primality Test

The Fermat primality test leverages consequences of Lagrange’s theorem in finite groups, specifically within the multiplicative group of integers modulo $n$.

Group Theoretic Foundations

Consider the set ${\mathbb{Z}}_n^{\ast }=\{a\in \{1,\dots ,n-1\}\mid \gcd (a,n)=1\}$. This set forms a finite abelian group under multiplication modulo $n$.

The group properties are:

• Closure: If $a,b\in {\mathbb{Z}}_n^{\ast }$, then $\gcd (ab,n)=1$, so $ab\mathrm{mod}n\in {\mathbb{Z}}_n^{\ast }$.
• Associativity: Multiplication modulo $n$ is associative.
• Identity Element: $1\in {\mathbb{Z}}_n^{\ast }$ serves as the identity, as $1\cdot a\equiv a\cdot 1\equiv a(\mathrm{mod}n)$.
• Inverse Element: For each $a\in {\mathbb{Z}}_n^{\ast }$, since $\gcd (a,n)=1$, Bézout’s identity guarantees the existence of integers $s,t$ such that $as+nt=1$. Thus, $as\equiv 1(\mathrm{mod}n)$, meaning $s\mathrm{mod}n$ is the multiplicative inverse of $a$ in ${\mathbb{Z}}_n^{\ast }$.

The order of this group, denoted $|{\mathbb{Z}}_n^{\ast }|$, is given by Euler’s totient function, $\varphi (n)$. For example, for $n=9$, ${\mathbb{Z}}_9^{\ast }=\{a\in \{1,\dots ,8\}\mid \gcd (a,9)=1\}=\{1,2,4,5,7,8\}$. The order is $|{\mathbb{Z}}_9^{\ast }|=\varphi (9)=9(1-1/3)=6$.

A fundamental result from group theory is Lagrange’s Theorem, which states that if $H$ is a subgroup of a finite group $G$, then the order of $H$, $|H|$, divides the order of $G$, $|G|$.

An important consequence relates to the order of an element $a\in G$, denoted $\text{ord}(a)$, which is the smallest positive integer $k$ such that $a^k=1$ (the identity element). The set $⟨a⟩=\{a^1,a^2,\dots ,a^{\text{ord}(a)}=1\}$ forms a cyclic subgroup generated by $a$, with order $\text{ord}(a)$. By Lagrange’s Theorem, $\text{ord}(a)$ must divide $|G|$.

Applying this to ${\mathbb{Z}}_n^{\ast }$, for any $a\in {\mathbb{Z}}_n^{\ast }$, $\text{ord}(a)$ divides $\varphi (n)$. This implies that $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$. This result is known as Euler’s Totient Theorem.

Fermat’s Little Theorem

Fermat’s Little Theorem is a special case of Euler’s Totient Theorem. If $n$ is a prime number, then every integer $a$ such that $1\le a<n$ is coprime to $n$.

Thus, ${\mathbb{Z}}_n^{\ast }=\{1,2,\dots ,n-1\}$, and its order is $\varphi (n)=n-1$.

Euler’s theorem then directly yields Fermat’s Little Theorem: If $n$ is prime and $a$ is an integer not divisible by $n$ (i.e., $a\in {\mathbb{Z}}_n^{\ast }$), then $a^{n-1}\equiv 1(\mathrm{mod}n)$.

The Fermat Test Algorithm

Fermat’s Little Theorem provides a basis for a primality test. If $n$ were prime, then $a^{n-1}\equiv 1(\mathrm{mod}n)$ should hold for any $a$ not divisible by $n$.

The Fermat primality test for a given integer $n>1$ proceeds as follows:

1. Choose a random integer $a$ in the range $2\le a\le n-2$. (Values $1$ and $n-1$ are avoided as $1^{n-1}\equiv 1$ and $(n-1{)}^{n-1}\equiv (-1{)}^{n-1}$ are often $1(\mathrm{mod}n)$ for composites too.)
2. Compute $\gcd (a,n)$. If $\gcd (a,n)>1$, then $n$ has a non-trivial factor $a$ (or a factor of $a$), so $n$ is composite.
3. If $\gcd (a,n)=1$, compute $x=a^{n-1}\mathrm{mod}n$ (typically using fast modular exponentiation).
4. If $x\not\equiv 1(\mathrm{mod}n)$, then $n$ violates Fermat’s Little Theorem, so $n$ must be composite. Such an $a$ is called a Fermat witness to the compositeness of $n$.
5. If $x\equiv 1(\mathrm{mod}n)$, then $n$ behaves like a prime for this base $a$. In this case, $n$ is declared “probably prime”.

Error Analysis of the Fermat Test

If $n$ is prime, then by Fermat’s Little Theorem, $a^{n-1}\equiv 1(\mathrm{mod}n)$ for all $a\in \{1,\dots ,n-1\}$. So, a prime number will always pass the test (be declared “probably prime”), assuming $\gcd (a,n)=1$ which is true for these $a$.

If $n$ is composite, the test can still pass. If $a^{n-1}\equiv 1(\mathrm{mod}n)$ for a composite $n$ and a base $a$ with $\gcd (a,n)=1$, then $a$ is called a Fermat liar for $n$, and $n$ is a Fermat pseudoprime to base $a$.

The critical weakness of the Fermat test lies with Carmichael numbers. These are composite numbers $n$ such that $a^{n-1}\equiv 1(\mathrm{mod}n)$ for all integers $a$ with $\gcd (a,n)=1$.

For such numbers, the Fermat test will declare them “probably prime” for any chosen base $a$ coprime to $n$, making the test completely ineffective. The smallest Carmichael number is $561=3\cdot 11\cdot 17$.

Formally, let $P{B}_n=\{a\in {\mathbb{Z}}_n^{\ast }\mid a^{n-1}\equiv 1(\mathrm{mod}n)\}$. This set $P{B}_n$ is the set of Fermat liars in ${\mathbb{Z}}_n^{\ast }$. It can be shown that $P{B}_n$ is a subgroup of ${\mathbb{Z}}_n^{\ast }$.

A composite number $n$ is a Carmichael number if and only if $P{B}_n={\mathbb{Z}}_n^{\ast }$.

If $n$ is composite and not a Carmichael number, then $P{B}_n$ is a proper subgroup of ${\mathbb{Z}}_n^{\ast }$. By Lagrange’s Theorem, the order of this subgroup $|P{B}_n|$ must divide $|{\mathbb{Z}}_n^{\ast }|$, so $|P{B}_n|\le \frac{1}{2}|{\mathbb{Z}}_n^{\ast }|$.

The probability of error (picking an $a\in \{2,\dots ,n-2\}$ that is a Fermat liar) is $\frac{|P{B}_n|-1}{n-3}$ if we consider choices from $2,..,n-2$ or more simply, if $a$ is chosen uniformly from ${\mathbb{Z}}_n^{\ast }$, the probability of picking a liar is $|P{B}_n|/|{\mathbb{Z}}_n^{\ast }|\le 1/2$. If $a$ is chosen from $\{1,\dots ,n-1\}$, the error probability $\frac{|P{B}_n|}{n-1}$ is at most $\frac{\varphi (n)/2}{n-1}$, which is generally less than $1/2$.

It’s commonly stated that for a non-Carmichael composite $n$, the probability of error is at most $1/2$. Repeating the test $t$ times with independent random bases reduces this error probability to at most $(1/2{)}^t$.

The Miller-Rabin Primality Test

The Miller-Rabin test is a more sophisticated probabilistic primality test that strengthens the Fermat test by also checking for non-trivial square roots of 1 modulo $n$. This allows it to correctly identify Carmichael numbers as composite.

The Key Principle: Square Roots of Unity Modulo a Prime

A crucial property used by the Miller-Rabin test is: if $n$ is a prime number, the only solutions to the congruence $x^2\equiv 1(\mathrm{mod}n)$ are $x\equiv 1(\mathrm{mod}n)$ and $x\equiv -1(\mathrm{mod}n)$. This is because $x^2-1\equiv 0(\mathrm{mod}n)$ implies $(x-1)(x+1)\equiv 0(\mathrm{mod}n)$. Since $n$ is prime, $n$ must divide $(x-1)$ or $n$ must divide $(x+1)$. Thus, $x\equiv 1(\mathrm{mod}n)$ or $x\equiv -1(\mathrm{mod}n)$. If $n$ is composite, there can be other solutions. For example, if $n=pq$ (distinct primes), then $x^2\equiv 1(\mathrm{mod}pq)$ can have four solutions. The Miller-Rabin test exploits this: if it finds an $x\not\equiv \pm 1(\mathrm{mod}n)$ such that $x^2\equiv 1(\mathrm{mod}n)$, then $n$ must be composite.

Algorithmic Setup

Let $n>2$ be an odd integer we want to test for primality (even numbers are easily handled).

First, write $n-1$ in the form $2^{k}d$, where $d$ is odd and $k\ge 1$ (since $n-1$ is even).

For a chosen base $a$ (where $2\le a\le n-2$), consider the sequence of values: $x_0=a^d(\mathrm{mod}n)$ $x_1=x_0^2=a^{2d}(\mathrm{mod}n)$ $x_2=x_1^2=a^{4d}(\mathrm{mod}n)$ $\dots$ $x_k=x_{k-1}^2=a^{2^{k}d}=a^{n-1}(\mathrm{mod}n)$

If $n$ is prime, then by Fermat’s Little Theorem, $a^{n-1}\equiv 1(\mathrm{mod}n)$, so $x_k\equiv 1(\mathrm{mod}n)$.

Now, consider this sequence $x_0,x_1,\dots ,x_k$.

If $n$ is prime, one of two conditions must hold:

1. $x_0=a^d\equiv 1(\mathrm{mod}n)$.
2. Or, there exists some $i\in \{0,1,\dots ,k-1\}$ such that $x_i=a^{2^{i}d}\equiv -1(\mathrm{mod}n)$. If this is true, then $x_{i+1}=(x_i{)}^2\equiv (-1{)}^2\equiv 1(\mathrm{mod}n)$, and all subsequent terms $x_j$ for $j>i$ will also be 1.

If neither of these conditions is met, $n$ cannot be prime. Specifically, if $x_k=a^{n-1}\equiv 1(\mathrm{mod}n)$ but for all $i\in \{0,\dots ,k-1\}$, $x_i\not\equiv -1(\mathrm{mod}n)$, and also $x_0\not\equiv 1(\mathrm{mod}n)$, then there must be some $x_j\equiv 1(\mathrm{mod}n)$ for $j\in \{1,\dots ,k\}$ whose predecessor $x_{j-1}$ was not $\pm 1(\mathrm{mod}n)$. This $x_{j-1}$ would be a non-trivial square root of $1(\mathrm{mod}n)$, proving $n$ is composite. If $x_k=a^{n-1}\not\equiv 1(\mathrm{mod}n)$, then $n$ is composite by Fermat’s test itself.

The Miller-Rabin Test Algorithm

Given an odd integer $n>2$ to test and a base $a\in \{2,\dots ,n-2\}$:

1. Handle trivial cases: If $n=2$, it is prime. If $n$ is even (and $n>2$) or $n=1$, it is composite. (This algorithm assumes $n$ is odd and $n>2$.)
2. Find integers $k\ge 1$ and $d$ (odd) such that $n-1=2^{k}d$.
3. Compute $x=a^d\mathrm{mod}n$.
4. If $x=1$ or $x=n-1$ (which is $\equiv -1(\mathrm{mod}n)$), then $n$ passes the test for this base $a$ and is declared “probably prime”.
5. Otherwise (if $x\ne 1$ and $x\ne n-1$), proceed to iterate $k-1$ times (for $j$ from $1$ to $k-1$):
   1. Set $x\leftarrow x^2\mathrm{mod}n$. (This computes $a^{2d},a^{4d},\dots ,a^{2^{k-1}d}(\mathrm{mod}n)$).
   2. If $x=n-1$, then $n$ passes the test for base $a$ and is declared “probably prime”. (We found an $a^{2^{j}d}\equiv -1(\mathrm{mod}n)$).
   3. If $x=1$, then the previous value of $x$ (which was $a^{2^{j-1}d}$) was neither $1$ nor $n-1$, but its square is $1$. Thus, $n$ has a non-trivial square root of $1$, so $n$ is composite.
6. If the loop completes (meaning $x$ was never $n-1$ in step 5.2, and never $1$ in step 5.3 after $x_0\ne \pm 1$), then $n$ is composite. (This implies that either $a^{n-1}\not\equiv 1(\mathrm{mod}n)$, or $a^{n-1}\equiv 1(\mathrm{mod}n)$ but we have $a^{2^{k-1}d}\not\equiv \pm 1(\mathrm{mod}n)$, which makes $a^{2^{k-1}d}$ a non-trivial square root of 1, or $a^{d\cdot 2^i}\not\equiv -1(\mathrm{mod}n)$ for any $i<k$ and $a^d\not\equiv 1(\mathrm{mod}n)$.)

Strength and Error Bound of Miller-Rabin Test

The Miller-Rabin test is a significant improvement over the Fermat test.

If $n$ is prime, it will always correctly declare $n$ “probably prime” for any base $a$. If $n$ is composite, the probability that the Miller-Rabin test incorrectly declares $n$ “probably prime” (i.e., $a$ is a strong liar for $n$) is at most $1/4$. This bound holds for all composite $n$, including Carmichael numbers.

By repeating the test $t$ times with $t$ independent random bases $a$, the probability of error (falsely declaring a composite $n$ as prime) can be reduced to at most $(1/4{)}^t$. This makes it a very reliable probabilistic primality test for practical purposes.

In summary, while the Fermat test is conceptually simpler and faster for a single iteration if $n-1$ is used directly, its failure on Carmichael numbers is a critical flaw. The Miller-Rabin test, by more deeply investigating the structure of square roots of unity modulo $n$, provides a much stronger guarantee of correctness, effectively handling Carmichael numbers and offering a low, bounded error probability for all composite numbers.

Continue here: 19 Long-Path Problem and Reduction to Hamiltonian Cycle, Solving Hamiltonian Cycle using DP, Long-Path via Randomized Coloring