The Fermat primality test

After several long tangents writing about orthogons and the chromatic number of the plane, I’m finally getting back to writing about primality testing. All along in this series, my ultimate goal has been to present some general primality testing algorithms and the math behind them, and now we’re finally ready to see our first (sort of!). As a reminder, and as a guide for anyone reading this without reading the previous posts, here’s the story so far:

So let’s see our first primality testing machine! This one is actually very simple. Remember that Fermat’s Little Theorem (the first version) says:

If p is prime and a is an integer where 0 < a < p, then a^{p-1} \equiv 1 \pmod p.

We can turn this directly into a test for primality, as follows: given some number n that we want to test for primality, pick an integer a between 0 and n (say, randomly), and compute a^{n-1} \pmod n. If the result is not equal to 1, then n is definitely not prime, since it would contradict Fermat’s Little Theorem. In that case we can immediately stop and report that n is composite (though note that we have not found any factors!).

(In actual practice, we don’t bother trying a = 1 or a = n-1; we only pick from 1 < a < n-1. Can you see why it’s useless to test a = 1 or a = n-1?)

For example, suppose we want to test n = 8. Let’s pick a = 2. We compute a^{n-1} = 2^7 = 128 \equiv 0 \pmod 8; hence n = 8 is not prime (but you probably knew that already). In this particular exampe a is actually a factor of n, but it need not be. For example, let n = 15 and pick a = 7; then computing 7^{14} \equiv 4 \pmod {15} proves that n is composite, even though 7 and 15 share no common factors.

So what if a^{n-1} is equivalent to 1 \pmod n? Unfortunately, Fermat’s Little Theorem is not an “if and only if” statement! It is quite possible to have a^{n-1} \equiv 1 \pmod n even when n is composite. So if we do get a result of 1, we simply can’t conclude anything about n. For example, with n = 15 again, if we happened to pick a = 4 instead of a = 7, then we get 4^{14} \equiv 1 \pmod {15} even though 15 isn’t prime.

So suppose we pick some a and get a^{n-1} \equiv 1 \pmod n. What can we do? Well, just try another a! If we get a^{n-1} \not\equiv 1 \pmod n for the new a, stop and report that n is composite. Otherwise, pick another a, and so on.

In general, we can iterate some fixed number of times k. If we ever find an a such that a^{n-1} \not\equiv 1 \pmod n, then we can report that n is definitely not prime. Otherwise, if we get through testing k different values of a and they all yield 1, then we can report that n is probably prime.

So this is better than nothing, but it’s not quite a primality machine, because it can’t tell us for sure that a number is prime. And it leaves a lot more questions: could we make k big enough so that we could know for sure whether n is prime? How big would k have to be? What about for composite numbers; how fast do we expect this to be? Are there other ways to build on this basic idea to get better (faster, more certain) primality tests? I’ll write about all this and more in future posts!

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in computation, number theory, primes and tagged , , . Bookmark the permalink.

4 Responses to The Fermat primality test

  1. Mark James says:

    You also need to be careful about Carmichael numbers. (https://en.wikipedia.org/wiki/Carmichael_number)

    For example, 561 will pass the FLT test a little more than 50% of the time.

  2. Pingback: Modular exponentiation | The Math Less Traveled

  3. Pingback: Modular exponentiation by repeated squaring | The Math Less Traveled

Leave a reply. You can include LaTeX $latex like this$. Note you have to literally write 'latex' after the first dollar sign!

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

WordPress.com Logo

You are commenting using your WordPress.com 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

This site uses Akismet to reduce spam. Learn how your comment data is processed.