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 divides (trial division). This algorithm appears to operate in linear time (perhaps faster if we only check numbers up to ), 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, is the value of the input. Since it takes bits to represent the number , our time complexity is actually
which is exponential in the size of the input. Though deterministic and unconditional primality testing algorithm is in (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.
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 is prime and is coprime to , then . This theorem holds for all numbers since, by definition of primality, 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 is in fact prime, the algorithm will always correctly identify it as prime, as FLT will certainly hold. If is composite, however, our algorithm may not be correct. Specifically, we may encounter a "Fermat liar": such that . For example, we have
although 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 is a composite, but not a Carmichael number1, then this algorithm outputs “composite” (i.e. is correct) with .
For clarity, we're sampling from (algebraic notation for the integers modulo ).
We call a number a "Fermat witness" if . Put simply, it's a number for which FLT fails, proving is composite. How many more Fermat liars are there than witnesses in ? 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 is composite (and not a Carmichael number) there exists at least one Fermat witness, which we denote . Multiplying any Fermat liar by results in a Fermat witness, as shown below for an arbitrary Fermat liar .
So we know every Fermat liar maps to a Fermat witness by the function . Whats more interesting, however, is that this is an injective mapping:
Note is coprime to 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 are Fermat witnesses--values that correctly identify as composite. Since our algorithm picks an integer at random, we can conclude that our probability of correctness if is compositive and not Carmichael is at least .
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 for trials, which achieves a 99% correctness rate in under 10 trials!
A single call to Fermat primality is dominated by the exponentiation and modulation operations, which are done in time. Running for trials we have a runtime of , which is highly efficient.
Carmichael numbers, of which there are infinitely many, are the Achilles' heel of Fermat primality testing. A Carmichael number is a composite number that satisfies the property for all integers coprime to . In fact, Carmichael numbers contradict the converse of FLT and prevent it from being an absolute test. ↩