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.


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.


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



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:


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 and there are only 22 of them below 10000 and 5597 of them below 10^9 (see 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.


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 = (6+ 1)(12+ 1)(18+ 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:


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.


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?


This entry was posted in Uncategorized and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s