Randomized Primality Testing with Monte Carlo Algorithms

2025-05-14

Motivation

Prime numbers are incredibly important for a lot of things in math: factoring, p-groups, modular arithmetic, etc. Many fields in computer science build upon these principles by applying them to areas like security and cryptography. Naturally, we find it important to check whether a number is prime.

The naive algorithm for "primality testing" involves checking whether every number up to n−1n-1 divides nn (trial division). This algorithm appears to operate in linear time (perhaps faster if we only check numbers up to n\sqrt{n}), but it actually doesn't have a polynomial time complexity. Formally speaking, time complexity is measured with respect to the size of the input, and in this case, nn is the value of the input. Since it takes log⁡n\log{n} bits to represent the number nn, our time complexity is actually

O(2log⁡n)O(2^{\log n})

which is exponential in the size of the input. Though deterministic and unconditional primality testing algorithm is in PP (AKS Primality Test) it's still pretty slow, especially when numbers are incredibly large. We're often faced with tasks like primality testing that are inefficient to deterministically compute; exploiting number theory and probability can lead us to more efficient solutions, though at some cost.

Most commonly used randomized algorithms are either Las Vegas algorithms or Monte Carlo algorithms. The former answers a query correctly and has a probabilistic runtime (e.g. QuickSelect) while the latter might get the answer wrong but has a fixed runtime (e.g. Primality Testing). This note will cover one type of a Monte Carlo algorithm with one-sided error: the Fermat primality test.

Algorithm

In general, our goal is to find some mathematical property that holds for prime numbers but necessarily doesn't for composites--we'll exploit such a property to quickly determine whether a number is prime.

Fermat's Little Theorem (FLT) states that if pp is prime and aa is coprime to pp, then ap−1≡1  (mod  p)a^{p-1} \equiv 1 \; (\text{mod} \;p). This theorem holds for all numbers ∈{2,…,p−1}\in \{2,\dots,p-1\} since, by definition of primality, pp has no factors. Using this fact, we develop the following algorithm:

FermatPrimality(N):
	Uniformly pick x in {1,...,N-1}
	if x^(N-1) % N = 1:
		return PRIME
	return COMPOSITE

If NN is in fact prime, the algorithm will always correctly identify it as prime, as FLT will certainly hold. If NN is composite, however, our algorithm may not be correct. Specifically, we may encounter a "Fermat liar": bb such that bN−1≡1  (mod  N)b^{N-1} \equiv 1 \; (\text{mod} \;N). For example, we have

21386≡1  (mod  1387)2^{1386} \equiv 1 \; (\text{mod} \;1387)

although 13871387 is not a prime number. Our algorithm may pick such a Fermat liar, and erroneously report "PRIME." With what probability will this occur? We'll prove the following statement: if NN is a composite, but not a Carmichael number1, then this algorithm outputs “composite” (i.e. is correct) with p≥12p \geq \frac{1}{2}.

Proof of Pr⁡[correct]≥12\Pr[\text{correct}] \geq \frac{1}{2}

For clarity, we're sampling from Z/NZ\mathbb{Z} / N\mathbb{Z} (algebraic notation for the integers modulo NN).

We call a number gg a "Fermat witness" if gN−1≢1  (mod  N)g^{N-1} \not\equiv 1 \; (\text{mod} \;N). Put simply, it's a number for which FLT fails, proving NN is composite. How many more Fermat liars are there than witnesses in Z/NZ\mathbb{Z} / N\mathbb{Z}? If we can compare the set of Fermat liars to Fermat witnesses, we can deduce this algorithm's one-sided correctness as we're sampling uniformly from the union of these sets.

Since NN is composite (and not a Carmichael number) there exists at least one Fermat witness, which we denote gg. Multiplying any Fermat liar by gg results in a Fermat witness, as shown below for an arbitrary Fermat liar bb.

(gb)n−1≡gn−1bn−1≡gn−1⋅1≡gn−1≢1  (mod  N).(gb)^{n-1} \equiv g^{n-1} b^{n-1} \equiv g^{n-1} \cdot 1 \equiv g^{n-1} \not\equiv 1 \; (\text{mod} \;N).

So we know every Fermat liar maps to a Fermat witness by the function f(b)=gbf(b)=gb. Whats more interesting, however, is that this is an injective mapping:

f(b1)=f(b2)  ⟹  gb1≡gb2  (mod  N)g−1gb1≡g−1gb2  (mod  N)b1≡b2  (mod  N)b1=b2.\begin{align*} f(b_1) = f(b_2) \implies gb_1 &\equiv gb_2 \; (\text{mod} \;N) \\ g^{-1} gb_1 &\equiv g^{-1} gb_2 \; (\text{mod} \;N) \\ b_1 &\equiv b_2 \; (\text{mod} \;N) \\ b_1 &= b_2. \end{align*}

Note gg is coprime to NN by virtue of being a witness, allowing us to cancel it via it's modular inverse. This one-to-one mapping implies that at least half the numbers in Z/NZ\mathbb{Z} / N\mathbb{Z} are Fermat witnesses--values that correctly identify NN as composite. Since our algorithm picks an integer at random, we can conclude that our probability of correctness if NN is compositive and not Carmichael is at least 12\frac{1}{2}.

Maybe this isn't so impressive. It's not much better than flipping a coin, right? But remember we only sampled one value to test. If we ran several independent trials (a technique called boosting), the probability we'd be incorrect across all consecutive runs is around 1−(12)t1-\left( \frac{1}{2} \right)^t for tt trials, which achieves a 99% correctness rate in under 10 trials!

Runtime

A single call to Fermat primality is dominated by the exponentiation and modulation operations, which are done in O(log⁡2nlog⁡log⁡n)O(\log^2 n \log \log n) time. Running for kk trials we have a runtime of O(klog⁡2nlog⁡log⁡n)O(k\log^2 n \log \log n), which is highly efficient.

Footnotes

  1. Carmichael numbers, of which there are infinitely many, are the Achilles' heel of Fermat primality testing. A Carmichael number is a composite number cc that satisfies the property bc−1≡  (mod  c)b^{c-1} \equiv \; (\text{mod} \;c) for all integers bb coprime to cc. In fact, Carmichael numbers contradict the converse of FLT and prevent it from being an absolute test. ↩