Primality Tests I

Description of Problem

The main problem we wish to discuss is as follows.

Question. Given n, how do we determine if it is prime?

Prime numbers have opened up huge avenues in theoretical research – the renowned Riemann Hypothesis, for example, is really a statement about the distribution of primes. On the other hand, it was only in the late 70s that people have found applications for them in computer science. Specifically, the RSA asymmetric encryption system requires the software to quickly generate huge prime numbers of several hundred digits. Hence, primality testing is of huge practical importance as well – in fact, without fast primality testing algorithms, asymmetric encryption systems would be totally absent.

[ Current state-of-the-art asymmetric encryption systems include RSA, Diffie-Hellman and elliptic curve cryptography, all of which rely heavily on the ability to generate huge primes quickly, among other things. ]

Curiously, primality testing turns out to be a much simpler problem than the task of factoring, where one needs to factor a given large integer. The current best algorithm for the latter task, general number field sieve, is extremely involved and requires an understanding of algebraic number theory. In contrast, most primality testing algorithms require only elementary number theory (except for the elliptic curve primality proving method, which I’ve yet to decide if I will cover).

Trial Division

One obvious way to test if a number is prime is trial division. Thus, given n, we iteratively test whether n is divisible by k, for all $k\le [\sqrt n]$ .

Why $[\sqrt n]$ ? Because if n is divisible by some k, it is also divisible by n/k. Thus we may assume one of the factors to be at most $\sqrt n$ . For example, given 103, we quickly find that it is prime since it is not divisible by 2, 3, …, 10.

In fact, if n is composite, then it is divisible by some prime number less than $\sqrt n$ . However, iterating through prime numbers is computationally difficult so one usually doesn’t bother with that. On the other hand, this gives us a quick way to mentally test if n is prime for n < 400, since we only need to test for possible factors 2, 3, 5, 7, 11, 13, 17, 19.

Trial division is impractical for large numbers, but don’t knock it! When you need to code a quick function to test if a 32-bit number is prime, trial division is the way to go.

blue-lin

Fermat Test

The primary observation comes from the following number-theoretic result:

Fermat’s (Little) Theorem.

If $p$ is prime and $a$ is an integer not divisible by $p$ , then

$a^{p-1} \equiv 1 \pmod p.$

Thus the contrapositive statement says: if a is an integer not divisible by p and $a^{p-1} \not\equiv 1 \pmod p$ , then p is not prime. This is called the Fermat test with base a. As example 2 below shows, it has its flaws.

Example 1

Consider the integer n = 15943. Picking a = 2, we have:

$2^{15942} \equiv 5086 \not\equiv 1\pmod {15943}.$

Hence n is composite.

Example 2

Consider the integer n = 10585. Fermat test then gives us

$\begin{aligned} 2^{10584} &\equiv 1 \pmod {10585},\\ 3^{10584} &\equiv 1 \pmod {10585}, \\ 5^{10584} &\equiv 4235 \not\equiv 1 \pmod {10585}.\end{aligned}$

Hence we see that n is composite. More importantly, this shows that Fermat test can fail for some bases.

Example 3

Let n = 10891. We see that:

$2^{10890} \equiv 3^{10890} \equiv 5^{10890} \equiv 7^{10890} \equiv 1 \pmod {10891}.$

Hence n appears to be prime. Indeed it is, as you can easily verify.

In summary, we have the following:

Fermat Test for n.

For various positive bases $a<n$ , we check if $a^{n-1} \equiv 1 \pmod n.$ If this fails for any a, we know that n is composite. Otherwise, n is most probably prime.

Exercise

Explain why, in the Fermat test, if we wish to test for all bases < A, it suffices to test for all prime bases < A.

blue-lin

Pseudoprimes

Example 2 above teaches us an important lesson: there are composite n and numbers a≠1 for which $a^{n-1}\equiv 1 \pmod n.$ Hence we have:

Definition.

If $n$ is composite and $a\ne 1$ is such that $a^{n-1} \equiv 1 \pmod n$ , then we say $n$ is a pseudoprime with base $a$ .

For a fixed base, pseudoprimes are rather rare. For example, the list of pseudoprimes with base 2 can be obtained on https://oeis.org/A001567 and there are only 22 of them below 10000 and 5597 of them below $10^9$ (see http://oeis.org/A055550). Hence given a random huge composite number, chances are high that the first Fermat test will expose it. Put in another way, given a huge random number that passes the first Fermat test, chances are high it’s prime.

This seems to imply that if a large integer n passes (say) 30 Fermat tests, then it’s guaranteed to be prime.

Not really, for we have the following.

Definition.

If $n$ is composite such that for all $a$ coprime to $n$ we have $a^{n-1} \equiv 1 \pmod n,$ then we say $n$ is a Carmichael number.

The smallest Carmichael number is 561 = 3 × 11 × 17.

While such numbers are rare, there are infinitely many of them. [ Fun fact: this conjecture remained open for a long time and was finally proven in 1994, by Alford, Granville and Pomerance. ] Note, however, that among the list of Carmichael numbers, each term seems to have a small prime factor; for instance, 561 is divisible by 3. So maybe we can combine Fermat test with trial division (by small primes) in order to weed out such cases?

No such luck, however. Chernick discovered in 1931 that if k is a positive integer such that 6k+1, 12k+1 and 18k+1 are all prime, then

n = (6k + 1)(12k + 1)(18k + 1)

is a Carmichael number. Now, it remains an open question whether there are infinitely many Carmichael numbers of this form, but in practice (from what we know of density of primes), it is quite easy to construct extremely large Carmichael numbers of this form. For instance, it takes only a few seconds for a Python script to give us the following 301-digit Carmichael number with three 100-digit prime factors:

3678977776333017616618572124346263612335718264220592681275
4323375966931049703503059541656515082721932203861403966236
1707445079748715571482964640305403211055421233151364221297
3982555078692571752850813633662021955795733617868645037712
1505333087445948159695018394505386803232557678106811464742
96899444481

Such a case would have no hope of getting picked up by a combination of Fermat test and trial division. But don’t give up yet, for the story is not over.

Exercises

Prove Chernick’s result. [This is one of those results which are easy to prove, but hard to obtain.]

Extend Chernick’s result to obtain a Carmichael number of >400 digits which has four prime divisors. What about five?

blue-lin