Primality Test

Although no polynomial-time classical algorithm is known for computing the prime factorization of an integer, primality testing can be done in polynomial time. The central idea behind randomized primality testing is to search for a certificate of compositeness that can be verified efficiently.

In this note, we first review several number-theoretic primitives. Then we discuss Fermat's Test and explain why it fails on Carmichael numbers. Finally, we introduce the Miller--Rabin Test, which strengthens Fermat's Test by searching for nontrivial square roots of unity.

Throughout this note, for a positive integer $n$, we write

Number Theory Primitives

This section reviews several basic number-theoretic primitives that will be used later, including Bézout's Identity, Fermat's Little Theorem, and Lagrange's Theorem.

Bézout's Identity

Theorem. Given two positive integers $n$ and $m$, if

$$\gcd(n,m) = k,$$

then there exist integers $a,b \in \mathbb{Z}$ such that

$$an + bm = k.$$

Proof. Consider the set

Let

The value $c$ is well-defined because $n,m > 0$, and hence $n \in E$ and $m \in E$. In particular, we have

We first show that $c$ divides both $n$ and $m$. By the division algorithm, there exist integers $q$ and $r$ such that

Since $n \in E$ and $c \in E$, we also have

If $r > 0$, then $r$ is a positive element of $E$ smaller than $c$, contradicting the definition of $c$. Therefore, $r = 0$, and hence $c \mid n$. The same argument shows that $c \mid m$.

Thus, $c$ is a common divisor of $n$ and $m$. Moreover, every common divisor of $n$ and $m$ divides every element of $E$, and in particular divides $c$. Therefore, $c$ is the greatest common divisor of $n$ and $m$. Hence,

Since $c \in E$, there exist integers $a,b \in \mathbb{Z}$ such that

$\blacksquare$

Fermat's Little Theorem

Theorem. If $n$ is prime, then for every $x \in [n-1]$,

$$x^{n-1} \equiv 1 \pmod n.$$

Proof. Consider the sequence

We claim that these numbers are pairwise distinct modulo $n$.

Indeed, suppose that

for some $i,j \in [n-1]$. Then

Since $n$ is prime and $x \not\equiv 0 \pmod n$, it follows that

But $i,j \in [n-1]$, so this implies $i=j$.

Therefore, multiplication by $x$ permutes the nonzero residues modulo $n$. Hence,

Equivalently,

Since $n$ is prime, none of $1,2,\ldots,n-1$ is divisible by $n$. Thus, $(n-1)!$ has a multiplicative inverse modulo $n$. Canceling $(n-1)!$ from both sides gives

$\blacksquare$

Lagrange's Theorem

Theorem. If $Z$ is a finite group and $S$ is a subgroup of $Z$, then $|S|$ divides $|Z|$. Equivalently,

$$|Z| \equiv 0 \pmod{|S|}.$$

Proof. For each $z \in Z$, define the left coset of $S$ generated by $z$ as

We first show that every coset has the same size as $S$. Fix $z \in Z$. Consider the map

This map is injective: if $zx = zy$, then multiplying both sides on the left by $z^{-1}$ gives $x = y$. It is also surjective by the definition of $zS$. Therefore, $\phi_z$ is a bijection, and hence

Now consider the collection of all left cosets of $S$ in $Z$. We claim that distinct cosets are disjoint. Suppose that two cosets $zS$ and $wS$ have a common element. Then there exist $x,y \in S$ such that

Rearranging gives

Since $y,x^{-1} \in S$, we have $yx^{-1} \in S$. Thus, $z \in wS$.

We now show that $zS = wS$. For any $s \in S$,

Since $(yx^{-1})s \in S$, it follows that $zs \in wS$. Hence,

By symmetry,

Therefore,

Thus, the distinct left cosets of $S$ form a partition of $Z$. If there are $t$ distinct cosets, then each has size $|S|$, and therefore

Hence, $|S|$ divides $|Z|$.

$\blacksquare$

Fermat's Test

We begin with Fermat's Test, a simple randomized primality test. The test has one-sided error: if it outputs NO, then $n$ is definitely composite; if it outputs YES, then $n$ is only probably prime. The test can have false positives, but it works well for many composite numbers.

Algorithm: Fermat's Test

Input: An integer $n$ and a repetition parameter $T$.

Output: NO if $n$ is composite; YES if $n$ is probably prime.

1. If $n \le 1$, output NO.
2. If $n = 2$, output YES.
3. Repeat the following steps for $t = 1,2,\ldots,T$:
   1. Choose $x \in [n-1]$ uniformly at random.
   2. If $\gcd(x,n) \neq 1$, output NO.
   3. Check whether$$x^{n-1} \equiv 1 \pmod n.$$If not, output NO.
4. If all $T$ iterations pass, output YES.

We now analyze the algorithm. For an integer $n$, define

That is, $\mathbb{Z}_n^*$ is the set of nonzero residues modulo $n$ that are coprime to $n$.

The set $\mathbb{Z}_n^*$ forms a group under multiplication modulo $n$:

• The identity element $1$ belongs to $\mathbb{Z}_n^*$.
• If $x \in \mathbb{Z}_n^*$, then $\gcd(x,n)=1$. By Bézout's Identity, there exist integers $a,b \in \mathbb{Z}$ such that$$ax + bn = 1.$$Hence$$ax \equiv 1 \pmod n.$$Therefore, $a \bmod n$ is the multiplicative inverse of $x$ modulo $n$.
• If $x,y \in \mathbb{Z}_n^*$, then $\gcd(xy,n)=1$, so $xy \in \mathbb{Z}_n^*$.
• Multiplication modulo $n$ is associative.

Now consider the set of elements that satisfy Fermat's congruence:

The set $S$ is a subgroup of $\mathbb{Z}_n^*$.

Indeed:

• The identity element $1$ belongs to $S$.
• If $x,y \in S$, then$$(xy)^{n-1} \equiv x^{n-1} y^{n-1} \equiv 1 \pmod n.$$Hence $xy \in S$.
• If $x \in S$, then$$x^{n-1} \equiv 1 \pmod n.$$Taking inverses on both sides gives$$(x^{-1})^{n-1} \equiv 1 \pmod n.$$Hence $x^{-1} \in S$.

Therefore, $S$ is a subgroup of $\mathbb{Z}_n^*$. Since $\mathbb{Z}_n^*$ is finite, Lagrange's Theorem implies that

Suppose there exists some $x \in \mathbb{Z}_n^*$ such that

Then $S$ is a proper subgroup of $\mathbb{Z}_n^*$. By Lagrange's Theorem, this implies

Thus, at least half of the elements in $\mathbb{Z}_n^*$ fail Fermat's congruence.

Moreover, in the algorithm above, every $x \notin \mathbb{Z}_n^*$ is detected immediately by the gcd check. Therefore, if $S$ is a proper subgroup of $\mathbb{Z}_n^*$, then one iteration of Fermat's Test outputs NO with probability at least $1/2$.

However, a systematic source of error remains. There exist composite numbers $n$ such that every element coprime to $n$ satisfies Fermat's congruence:

Equivalently, for such numbers,

These composite numbers are called Carmichael numbers. The smallest example is

Thus, Fermat's Test can incorrectly output YES on Carmichael numbers. This motivates the Miller--Rabin Test, whose key idea is to search for a nontrivial square root of $1$ modulo $n$.

Miller--Rabin Test

Fermat's Test can fail on Carmichael numbers. The Miller--Rabin Test strengthens Fermat's Test by looking not only at whether

but also at the intermediate square roots of $1$ that appear during the computation.

The key observation is the following.

Nontrivial Square Roots of Unity Modulo a Prime

Lemma. If $n$ is prime and

$$x^2 \equiv 1 \pmod n,$$

then

$$x \equiv 1 \pmod n \qquad \text{or} \qquad x \equiv -1 \pmod n.$$

Here $-1 \pmod n$ denotes the residue $n-1$.

Proof. From

we have

Since $n$ is prime, it follows that

Therefore,

$\blacksquare$

Observe that when $n > 2$, the two residues $1$ and $-1$ are distinct modulo $n$.

Algorithm: Miller--Rabin Test

Input: An integer $n$ and a repetition parameter $T$.

Output: NO if $n$ is composite; YES if $n$ is probably prime.

1. If $n \le 1$, output NO.
2. If $n = 2$, output YES.
3. If $n$ is even, output NO.
4. If $n$ is a perfect power, output NO.
5. Write$$n-1 = 2^k m,$$where $m$ is odd.
6. Repeat the following steps for $t = 1,2,\ldots,T$:
   1. Choose $x \in [n-1]$ uniformly at random.
   2. If $\gcd(x,n) \neq 1$, output NO.
   3. Compute$$x^m, x^{2m}, x^{4m}, \ldots, x^{2^k m} \pmod n.$$
   4. If$$x^m \equiv 1 \pmod n,$$then this iteration passes.
   5. Otherwise, if there exists $i \in \{0,1,\ldots,k-1\}$ such that$$x^{2^i m} \equiv -1 \pmod n,$$then this iteration passes.
   6. Otherwise, output NO.
7. If all $T$ iterations pass, output YES.

Let us briefly justify the perfect-power check. If $n$ is a perfect power, then

for some integers $a \ge 2$ and $b \ge 2$. Since $a \ge 2$, we have

Therefore, it suffices to check every exponent

and test whether $n^{1/b}$ is an integer. This can be done in polynomial time, for example by binary search or integer root computation.

We now analyze the correctness of the test.

First, suppose $n$ is prime. By Fermat's Little Theorem,

for every $x \in [n-1]$. Since

we have

Consider the sequence

Each term is the square of the previous term. Since the last term is $1$, the sequence eventually reaches $1$. If the first term is already $1$, then the iteration passes. Otherwise, let $x^{2^j m}$ be the first term in the sequence that equals $1$. Then $j \ge 1$, and the previous term satisfies

Since $x^{2^{j-1}m} \not\equiv 1 \pmod n$, the previous lemma implies

Thus, the algorithm never outputs NO when $n$ is prime.

The main point is that when $n$ is composite, a random choice of $x$ is likely to reveal this.

Error Probability of the Miller--Rabin Test

Theorem. If $n$ is composite, then one iteration of the Miller--Rabin Test outputs YES with probability at most $1/2$. Therefore, after $T$ independent repetitions, the probability of incorrectly outputting YES is at most

$$2^{-T}.$$

Proof. Since the algorithm already rejects even numbers and perfect powers, we may assume that $n$ is odd and is not a perfect power.

Let

where $m$ is odd.

We call an element $x \in [n-1]$ a strong liar if one iteration of the Miller--Rabin Test outputs YES when using this value of $x$. Equivalently, $x$ is a strong liar if

or there exists some $i \in \{0,1,\ldots,k-1\}$ such that

Any strong liar must belong to $\mathbb{Z}_n^*$, because otherwise the gcd check would output NO.

We will show that all strong liars are contained in a proper subgroup of $\mathbb{Z}_n^*$. Then the desired probability bound follows from Lagrange's Theorem.

For each

define

Choose the largest value of $r$ among

such that there exists some $x \in \mathbb{Z}_n^*$ satisfying

Such an $r$ exists because $-1 \in \mathbb{Z}_n^*$ and, since $m$ is odd,

For this choice of $r$, define

We claim that $S$ has the following three properties:

1. Every strong liar belongs to $S$.
2. The set $S$ is a subgroup of $\mathbb{Z}_n^*$.
3. The subgroup $S$ is proper, i.e.,$$S \neq \mathbb{Z}_n^*.$$

Once these three properties are proved, the theorem follows immediately. Indeed, since $S$ is a proper subgroup of the finite group $\mathbb{Z}_n^*$, Lagrange's Theorem implies that

Since every strong liar belongs to $S$, we have

Therefore, when $x$ is chosen uniformly at random from $[n-1]$, one iteration outputs YES with probability at most $1/2$. Repeating the test independently $T$ times, the probability that all iterations output YES is at most

It remains to prove the three properties.

Property 1: Every strong liar belongs to $S$

Let $x$ be a strong liar. Then either

or there exists $i \in \{0,1,\ldots,k-1\}$ such that

If $x^m \equiv 1 \pmod n$, then since $r$ is a multiple of $m$,

so $x \in S$.

Otherwise, suppose

By the maximality of $r$, we have $2^i m \le r$. Since both $2^i m$ and $r$ are powers of two times $m$, $r/(2^i m)$ is a power of two. Hence

Thus $x \in S$.

Therefore, every strong liar belongs to $S$.

Property 2: $S$ is a subgroup of $\mathbb{Z}_n^*$

We show that $S$ satisfies the subgroup conditions.

First, the identity element belongs to $S$ because

Second, $S$ is closed under multiplication. If $x,y \in S$, then

Therefore,

Thus $xy \in S$.

Third, $S$ is closed under inverses. If $x \in S$, then

Taking inverses on both sides gives

Hence $x^{-1} \in S$.

Therefore, $S$ is a subgroup of $\mathbb{Z}_n^*$.

Property 3: $S$ is a proper subgroup of $\mathbb{Z}_n^*$

It remains to show that

We will construct an element $y$ such that

Since $n$ is composite, odd, and not a perfect power, $n$ has at least two distinct prime factors. Write

where $t \ge 2$. Let

Then

Moreover, since $n$ is odd, both $a$ and $b$ are odd, and hence

By the choice of $r$, there exists some $x \in \mathbb{Z}_n^*$ such that

Equivalently,

By the Chinese Remainder Theorem, there exists some $y \in [0, \ldots, n-1]$ such that

We first show that $y \notin S$. From the definition of $y$, we have

Thus $y^r$ cannot be congruent to $1$ modulo $n$, because modulo $a$ it is congruent to $-1$, not $1$. Similarly, $y^r$ cannot be congruent to $-1$ modulo $n$, because modulo $b$ it is congruent to $1$, not $-1$. Therefore,

Hence

We next show that $y \in \mathbb{Z}_n^*$. Since $x \in \mathbb{Z}_n^*$, we have

Because

we get

Also, since

we have

Since $n=ab$ and $\gcd(a,b)=1$, it follows that

Therefore,

We have found an element

Therefore,

So $S$ is a proper subgroup of $\mathbb{Z}_n^*$.

$\blacksquare$

Reference

1. Primality Testing, CS265/CME309, Fall 2017, Gregory Valiant