# An Introduction to Primality Testing

## Fred Akalin

I will explain two commonly-used primality tests: Fermat and
Miller-Rabin. Along the way, I will cover the basic concepts of
primality testing. I won't be assuming any background in number
theory, but familiarity
with modular
arithmetic will be helpful. I will also be providing
implementations in Javascript,
so familiarity
with it will also be helpful. Finally, since Javascript doesn't
natively support arbitrary-precision arithmetic, I wrote a simple
natural number class
(`SNat`

) that
represents a number as an array of decimal digits. All algorithms
used are the simplest possible, except when a more efficient one is
needed by the algorithms we discuss.

Primality testing is the problem of determining whether a given natural number is prime or composite. Compared to the problem of integer factorization, which is to determine the prime factors of a given natural number, primality testing turns out to be easier; integer factorization is in NP and thought to be outside P and NP-complete, whereas primality testing is now known to be in P.

Most primality tests are actually compositeness tests; they involve
finding *composite witnesses*, which are numbers that, along
with a given number to be tested, can be fed to some easily-computable
function to prove that the given number is composite. (The composite
witness, along with the function, is a *certificate of
compositeness* of the given number.) A primality test can either
check each possible witness or, like the Fermat and Miller-Rabin
tests, it can randomly sample some number of possible witnesses and
call the number prime if none turn out to be witnesses. In the latter
case, there is a chance that a composite number can erroneously be
called prime; ideally, this chance goes to zero quickly as the sample
size increases.

The simplest possible witness type is, of course, a factor of the
given number, which we'll call a *factor witness*. If the
number to be tested is \(n\) and the possible factor witness is \(a\),
then one can simply test whether \(a\) divides \(n\) (written as \(a
\mid n\)) by evaluating \(n \; \mathrm{mod} \; a = 0\); that is, whether the
remainder of \(n\) divided by \(a\) is zero. This doesn't yield a
feasible deterministic primality test, though, since checking all
possible witnesses is equivalent to factoring the given number. Nor
does it yield a feasible probabilistic primality test, since in the
worst case the given number has very few factors, which random
sampling would miss.

The simplest useful witness type is a *Fermat witness*,
which relies on the following theorem of Fermat:

(Fermat's little theorem.) If \(n\) is prime and \(a\) is not a multiple of \(n\), then \[ a^{n-1} \equiv 1 \; (\mathrm{mod} \; n)\text{.} \]

Thus, a Fermat witness is a number \(1 \lt a \lt n\) such that
\(a^{n-1} \neq 1 \; (\mathrm{mod} \; n)\). Conversely, if \(n\) is composite
and \(a^{n-1} \equiv 1 \; (\mathrm{mod} \; n)\), then \(a\) is a *Fermat
liar*.

Let
`n` =
and
`a` =
.

If \(n\) has at least one Fermat witness that is relatively prime, then we can show that at least half of all possible witnesses are Fermat witnesses. (Roughly, if \(a\) is the Fermat witness and \(a_1, a_2, \ldots, a_s\) are Fermat liars, then all \(a \cdot a_i\) are also Fermat witnesses.) Therefore, for a sample of \(k\) possible witnesses of \(n\), the probability of all of them being Fermat liars is \(\le 2^{-k}\), which goes to zero quickly enough to be practical.

However, there is the possibility that \(n\) is a composite number
with no relatively prime Fermat witnesses. These are
called *Carmichael
numbers*. Even though Carmichael numbers are rare, their
existence still makes the Fermat primality test unsuitable for some
situations, as when the numbers to be tested are provided by some
adversary.

Here is the Fermat compositeness test implemented in Javascript:

```
// Runs the Fermat compositeness test given n > 2 and 1 < a < n.
// Calculates r = a^{n-1} mod n and whether a is a Fermat witness to n
// (i.e., r != 1, which means n is composite). Returns a dictionary
// with a, n, r, and isCompositeByFermat, which is true iff a is a
// Fermat witness to n.
function testCompositenessByFermat(n, a) {
n = SNat.cast(n);
a = SNat.cast(a);
if (n.le(2)) {
throw new RangeError('n must be > 2');
}
if (a.le(1) || a.ge(n)) {
throw new RangeError('a must satisfy 1 < a < n');
}
var r = a.powMod(n.minus(1), n);
var isCompositeByFermat = r.ne(1);
return {
a: a,
n: n,
r: r,
isCompositeByFermat: isCompositeByFermat
};
}
```

Note that the algorithm depends on the efficiency
of *modular
exponentiation* when calculating \(a^{n-1} \; (\mathrm{mod} \; n)\). The
naive method is unsuitable since it requires \(\Theta(n)\) \(b\)-bit
multiplications, where \(b = \lceil \lg n \rceil\). `SNat`

uses repeated
squaring, which requires only \(\Theta(\lg n)\) \(b\)-bit
multiplications.

Another useful witness type is a *non-trivial square root of
unity mod \(n\)*; that is, a number \(a \neq \pm 1
\; (\mathrm{mod} \; n)\) such that \(a^2 \equiv 1 \; (\mathrm{mod} \; n)\). It is a theorem of
number theory that if \(n\) is prime, there are no non-trivial square
roots of unity mod \(n\). Therefore, if we do find one, that means
\(n\) is composite. In fact, finding one leads directly to factors of
\(n\). By definition, a non-trivial square root of unity \(a\)
satisfies \(a \pm 1 \neq 0 \; (\mathrm{mod} \; n)\) and \(a^2 - 1 \equiv 0
\; (\mathrm{mod} \; n)\). Factoring the latter leads to \((a+1)(a-1) \equiv 0
\; (\mathrm{mod} \; n)\), which means that \(n\) divides \((a+1)(a-1)\). But the
first condition says that \(n\) divides neither \(a+1\) nor \(a-1\),
so it must be a product of two numbers \(p \mid a+1\) and \(q \mid
a-1\). Then \(\gcd(a+1, n)\)^{[1]}
and \(\gcd(a-1, n)\) are factors of \(n\).

Finding non-trivial square roots of unity by itself doesn't give a useful primality testing algorithm, but combining it with the Fermat primality test does. \(a^{n-1} \; \mathrm{mod} \; n\) either equals \(1\) or not. If it doesn't, you're done since you have a Fermat witness. If it does equal \(1\), and \(n-1\) is even, then consider the square root of \(a^{n-1}\), i.e. \(a^{(n-1)/2}\). If it is not \(\pm 1\), then it is a non-trivial square root of unity. If it is \(-1\), then you can't do anything else. But if it is \(1\), and \((n-1)/2\) is even, you can then take another square root and repeat the test, stopping when the exponent of \(a\) becomes odd or when you get a result not equal to \(1\).

To turn this into an algorithm, you simply start from the bottom up: find the greatest odd factor of \(n-1\), call it \(t\), and keep squaring \(a^t\) mod \(n\) until you find a non-trivial square root of \(n\) or until you can deduce the value of \(a^{n-1}\). In fact, this is almost as fast as the original Fermat primality test, since the exponentiation by \(n-1\) has to do the same sort of squaring, and we're just adding comparisons to \(\pm 1\) in between squarings.

The original idea for the test above is from Artjuhov, although it
is usually credited to Miller. Therefore, we call \(a\) an *Artjuhov witness ^{[2]} of \(n\)* if it shows \(n\) composite by
the above test.

Let
`n` =
and
`a` =
.

If \(n\) is an odd composite, then it can be shown (originally by Rabin) that at least three quarters of all possible witnesses are Artjuhov witnesses. Therefore, for a sample of \(k\) possible witnesses of \(n\), the probability of all of them being Artjuhov liars is \(\le 4^{-k}\), which is stronger than the bound for the Fermat primality test. Furthermore, this bound is unconditional; there is nothing like Carmichael numbers for the Artjuhov test.

Here is the Artjuhov compositeness test, implemented in Javascript:

```
// Runs the Artjuhov compositeness test given n > 2 and 1 < a < n-1.
// Finds the largest s such that n-1 = t*2^s, calculates r = a^t mod
// n, then repeatedly squares r (mod n) up to s times until r is
// congruent to -1, 0, or 1 (mod n). Then, based on the value of s
// and the final value of r and i (the number of squarings),
// determines whether a is an Artjuhov witness to n (i.e., n is
// composite).
//
// Returns a dictionary with, a, n, s, t, i, r, rSqrt = sqrt(r) if i >
// 0 and null otherwise, and isCompositeByArtjuhov, which is true iff
// a is an Artjuhov witness to n.
function testCompositenessByArtjuhov(n, a) {
n = SNat.cast(n);
a = SNat.cast(a);
if (n.le(2)) {
throw new RangeError('n must be > 2');
}
if (a.le(1) || a.ge(n)) {
throw new RangeError('a must satisfy 1 < a < n');
}
var nMinusOne = n.minus(1);
// Find the largest s and t such that n-1 = t*2^s.
var t = nMinusOne;
var s = new SNat(0);
while (t.isEven()) {
t = t.div(2);
s = s.plus(1);
}
// Find the smallest 0 <= i < s such that a^{t*2^i} = 0/-1/+1 (mod
// n).
var i = new SNat(0);
var rSqrt = null;
var r = a.powMod(t, n);
while (i.lt(s) && r.gt(1) && r.lt(nMinusOne)) {
i = i.plus(1);
rSqrt = r;
r = r.times(r).mod(n);
}
var isCompositeByArtjuhov = false;
if (s.isZero()) {
// If 0 = i = s, then this reduces to the Fermat primality test.
isCompositeByArtjuhov = r.ne(1);
} else if (i.isZero()) {
// If 0 = i < s, then:
//
// * r = 0 (mod n) -> a^{n-1} = 0 (mod n), and
// * r = +/-1 (mod n) -> a^{n-1} = 1 (mod n).
isCompositeByArtjuhov = r.isZero();
} else if (i.lt(s)) {
// If 0 < i < s, then:
//
// * r = 0 (mod n) -> a^{n-1} = 0 (mod n),
// * r = +1 (mod n) -> a^{t*2^{i-1}} is a non-trivial square root of
// unity mod n, and
// * r = -1 (mod n) -> a^{n-1} = 1 (mod n).
//
// Note that the last case means r = n - 1 > 1.
isCompositeByArtjuhov = r.le(1);
} else {
// If 0 < i = s, then:
//
// * r = 0 (mod n) can't happen,
// * r = +1 (mod n) -> a^{t*2^{i-1}} is a non-trivial square root of
// unity mod n, and
// * r > +1 (mod n) -> failure of the Fermat primality test.
isCompositeByArtjuhov = true;
}
return {
a: a,
n: n,
t: t,
s: s,
i: i,
r: r,
rSqrt: rSqrt,
isCompositeByArtjuhov: isCompositeByArtjuhov
};
}
```

With the two compositeness tests above, we can now write a probabilistic primality test:

```
// Returns true iff a is a Fermat witness to n, and thus n is
// composite. a and n must satisfy the same conditions as in
// testCompositenessByFermat.
function hasFermatWitness(n, a) {
return testCompositenessByFermat(n, a).isCompositeByFermat;
}
// Returns true iff a is an Arjuhov witness to n, and thus n is
// composite. a and n must satisfy the same conditions as in
// testCompositenessByArtjuhov.
function hasArtjuhovWitness(n, a) {
return testCompositenessByArtjuhov(n, a).isCompositeByArtjuhov;
}
// Returns true if n is probably prime, based on sampling the given
// number of possible witnesses and testing them against n. If false
// is returned, then n is definitely composite.
//
// By default, uses the Artjuhov test for witnesses with 20 samples
// and Math.random for the random number generator. This gives an
// error bound of 4^-20 if true is returned.
function isProbablePrime(n, hasWitness, numSamples, rng) {
n = SNat.cast(n);
hasWitness = hasWitness || hasArtjuhovWitness;
rng = rng || Math.random;
numSamples = numSamples || 20;
if (n.le(1)) {
return false;
}
if (n.le(3)) {
return true;
}
if (n.isEven()) {
return false;
}
for (var i = 0; i < numSamples; ++i) {
var a = SNat.random(2, n.minus(2), rng);
if (hasWitness(n, a)) {
return false;
}
}
return true;
}
```

`isProbablePrime`

called
with `hasFermatWitness`

is the *Fermat primality
test*, and `isProbablePrime`

called
with `hasArtjuhovWitness`

is the *Miller-Rabin primality
test*. The latter is the current general primality test of
choice, replacing
the Solovay-Strassen
primality test.

We can also use `isProbablePrime`

to randomly generate
probable primes, which is useful
for cryptographic
applications:

```
// Returns a probable b-bit prime that is at least 2^b. All
// parameters but b are passed to isProbablePrime.
function findProbablePrime(b, hasWitness, rng, numSamples) {
b = SNat.cast(b);
var lb = (new SNat(2)).pow(b.minus(1));
var ub = lb.times(2);
while (true) {
var n = SNat.random(lb, ub);
if (isProbablePrime(n, hasWitness, rng, numSamples)) {
return n;
}
}
}
```

In this case, for sufficiently large \(b\), the Fermat primality
test is acceptable, since Carmichael numbers are so rare and we're the
ones generating the possible primes to be tested.^{[3]}

There are other primality tests, but they're less often used in
practice because they're
either less
efficient or more
sophisticated than the algorithms above, or they require \(n\) to
have special properties.
Perhaps the most interesting of these tests is
the *AKS
primality test*, which proved once and for all that primality
testing is in P.

[1] \(\gcd\) is the greatest common divisor function. ↩

[2] “Artjuhov witness” is an idiosyncratic
name on my part; a more common name is *strong witness*, which
I don't like.
↩

[3] According to Wikipedia, PGP uses the Fermat primality test. ↩