Fermat’s Primality Test

Remember our Bad Primality Testing algorithm? We chose 100 random numbers and divided a number by them to see if number was prime. This turned out to be a losing proposition. However, we can use a similar tactic that utilizes Fermat’s Little Theorem. This approach is called Fermat’s primality testing since it’s predicated upon Fermat’s Little Theorem. I’m going to unfold this algorithm one logical layer at a time, so bear with me.

We’ve already derived logically from Fermat’s Little Theorem that if we take a number N and run it through The Formula by plugging in some example of A and do not get a result of 1, then N must be composite.

Based on this, we can pick 100 random numbers to plug into the A variable, and run each example of A through The Formula. So, if N is 45,321, we’ll randomly pick 100 different example numbers for A, such as 3,453, 19,001, and 767, and test them out. If any of them produce a result that isn’t 1, we’ll know that N is composite.

However, if we get a result of 1 for all 100 tests, there’s a high likelihood that N is prime. This is because a composite number is unlikely to pass all 100 tests. (Soon, we’ll discuss precisely what the odds are.)

That being said, even when it passes 100 tests, N may in reality be composite. That is, N may in truth have some instances of A where the result of The Formula is 1 and other results where the result is not 1. However, we happened to be super unlucky and picked all the examples of A where The Formula will yield a 1. So, we’d mistakenly identify N as being prime even though it’s composite.

As such, this approach to primality testing is a Monte Carlo algorithm. The odds are high that N is prime, but there’s a small chance that it’s composite. Note, however, that the chance of error can only happen in one direction. That is, if The Formula ever produces a result other than 1, we can be 100 percent sure that N is composite. If, on the other hand, The Formula produces 100 instances of 1, although there are high odds that N is prime, we can’t be absolutely certain that it is so.

Fermat’s vs. Bad Primality Testing

Let’s dig in deeper. Why, exactly, is Fermat’s Primality Testing any better than our previous approach of Bad Primality Testing? After all, in both techniques we try out 100 computations using random numbers.

Here’s the answer. Let’s look again at what happens when we perform Bad Primality Testing. Say that we’re testing whether the number 47,957 is prime by dividing it by a smaller random number, such as 45, to see if there’s a remainder. If this doesn’t produce a remainder, we’d know that 47,957 is composite. But on the other side of the coin, if it does produce a remainder, what does that tell us about the probability of 47,957 being prime?

In truth, 47,957 is only divisible by the numbers 217 and 221. Indeed, many composite numbers are only divisible by a couple of smaller numbers. So the fact that we got a remainder when dividing 47,957 by 45 tells us almost nothing about the odds of whether 47,957 is prime. We’ve only eliminated one possible way in which 47,957 could be composite, but there may easily be other numbers that 47,957 is divisible by. And so, we’ve hardly moved the needle in seeing increased odds that 47,957 is prime.

However, each computation in Fermat’s Primality Testing that produces a 1 does significantly increase the odds that the number we’re testing is prime. Fermat never articulated the following statement, but other mathematicians did. This statement is the final piece of the puzzle:

If N is a composite number, each time we run The Formula, the chance of getting a result of 1 is 50 percent or less.

Let that sink in for a moment.

Recall that I pointed out that Fermat’s Little Theorem is one-directional. That is, if we run The Formula on a prime number N, there’s a 100 percent chance that we will get a result of 1. If N is composite, though, it may or may not produce a 1.

However, we’re filling in an additional detail now by saying that if N is composite, the odds of us getting a 1 for any time we run The Formula are 50/50. In truth, the mathematicians stated that the odds may be less than 50/50, but let’s call it 50/50 to simplify things.

Let’s see how this all plays out. If I test N against one example of A, and get a 1, I haven’t learned much. After all, there’s a 50/50 chance that N is composite.

But say I test N again.

And again.

And again.

This is like flipping a coin. It’s not remarkable when a coin lands on heads; there was a 50 percent chance that this would happen. But if I flip a coin many times and always get heads, that’s truly remarkable since such a result is very unlikely.

With Fermat’s Primality Testing, when we test N against 100 examples of A, it’s like flipping a coin 100 times. Sure, if N is composite, each “flip” has a 50 percent chance of yielding a 1. But if we make 100 flips for a composite number, it’s extremely unlikely that all 100 flips will produce a 1. This is like flipping a coin 100 times and always getting heads. (In math terms, we’d say the odds are 1/2¹⁰⁰.)

This is why Fermat’s Primality Testing is a highly effective algorithm. If we run The Formula 100 times on N and always get a 1, it is highly probable that N is prime.

And this, my friends, is how Fermat’s primality testing works. To sum it up:

To test N, we pick 100 random examples of A and run The Formula for each example. If we ever get a result that is not 1, we’ll know with 100 percent certainty that N is composite. And if we always get a 1, then it’s highly probable that N is prime.

Fermat’s primality testing is a solid Monte Carlo algorithm because it has a guaranteed speed of 100 tests, but it is not necessarily correct. However, because it’s highly probable to be correct, this algorithm can produce results that you might consider to be accurate enough for your particular application.

There’s one tiny caveat, though. We’ve gone through all the logical hoops of analyzing Fermat’s Little Theorem, except for one, which we’ll take a look at next.

Carmichael Numbers

Fermat asserted that if N is prime, if we run each and every example of A through The Formula, we’ll always get 1. We’ve deduced from this that if we ever get a result that isn’t 1, then N must be composite. We also saw that if we do get a result of 1, we can’t know for certain whether N is prime or composite. Even a composite number has a 50/50 chance of producing a 1 for each example of A.

But what happens if we methodically run The Formula for each and every A and always get 1? Fermat said that if N is prime, we’ll always get 1, but let’s analyze the converse. If we always get 1, does that mean that N is prime?

It turns out that it does not mean that N is certainly prime. For there are some composite numbers that will produce 1 each time we run The Formula—even for all instances of A.

These special composite numbers are called Carmichael Numbers, named after the mathematician Robert Carmichael, who researched these numbers in depth.

The smallest Carmichael Number is 561. The number 561 is composite, as 561/17=33. However, incredibly enough, if we run The Formula for all examples of A (that is, 1 through 560), the result will always be 1.

Carmichael Numbers throw a nice little monkey wrench into Fermat’s Primality Testing. The success of this testing relies on our assertion that the odds of The Formula computing a 1 for a composite number are no greater than 50 percent. However, this doesn’t hold true for Carmichael Numbers, as the chance of computing a result of 1 is 100 percent!

This being said, Fermat’s primality testing is still useful because Carmichael Numbers themselves are rare. From numbers 1 up until 25,000,000,000, there are only 2,163 Carmichael Numbers. Additionally, the frequency of Carmichael Numbers drops as we deal with higher and higher numbers.

In other words, we kind of incorporate the rarity of Carmichael Numbers into our Monte Carlo algorithm. That is, for a “regular,” non-Carmichael composite number, there’s a high probability that our 100 tests will reveal that it’s composite (by producing a number other than 1). And even though this isn’t the case for Carmichael Numbers, there’s a high probability that our number simply isn’t a Carmichael Number.

If you’ve decided that Carmichael Numbers have the potential to mess up your application, you’re still in luck. There are other primality testing algorithms—which are extensions of Fermat’s Primality Testing—that properly handle the edge case of Carmichael Numbers. Some such algorithms include the Miller–Rabin test and the Solovay–Strassen test. If this piques your interest, go check them out.

Code Implementation: Fermat’s Primality Test

The code for Fermat’s primality test is concise and simple:

To test the primality of number, we run a loop 100 times. In each iteration, we choose a random number a, representing what we’ve been calling “A”—which is the series of smaller numbers from 1 up until number.

Next, we compute The Formula to see if we get a remainder of 1. To accomplish this, we use the code:

This syntax may not be familiar to you, so here’s a brief explanation:

It turns out that Python has at least five different ways that you can calculate exponents. The most popular approach is the ** operator. If we take this approach, we can run The Formula using the code:

However, it turns out that the ** is unable to compute exponents using very large numbers. While this code worked fine when I tried to test the integer 563 for being prime, it flatly refused to cooperate when the number was 2147480219.

However, Python has other ways to compute exponents, including the built-in pow method. And fortunately, pow is able to process large primes like 2147480219.

The pow method accepts a minimum of two arguments, the first being the base number and the second being the exponent. However, pow comes with a super-convenient feature. It accepts an optional third argument that takes the result of computing the first two arguments and divides it by the third argument modulus style, giving us the remainder. In other words, pow(x, y, z) is the equivalent of x**y % z. And that’s exactly what we want!

If the result of this calculation is not 1, it means number is composite, so we return False. However, if after running The Formula 100 times we always get a result of 1, we assume with high probability that number is prime and so we return True.