Traveling Home

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:

• We first saw three different versions of Fermat’s Little Theorem (FlT), as well as a statement of Euler’s Theorem which is a generalization of FlT. Don’t worry if you don’t remember what Fermat’s Little Theorem says; I’ll remind you below. (As an aside, I recently learned there is yet a further generalization of Euler’s Theorem called Carmichael’s Theorem, but that will have to be another post for another time!)
• Just for fun, we saw three differenet proofs of FlT: by modular arithmetic, by combinatorics, and by group theory, as well as corresponding proofs of Euler’s Theorem.
• We then talked about three hypothetical machines for determining properties of a natural number : one to give the complete prime factorization, one to give a single factor, and one to say whether is prime. I also mentioned the (surprising) fact that it is possible to build relatively fast machines of the third type—that is, for doing primality testing—but as far as we know, any machines to find factors are much slower.
• Finally, we talked about what we really mean by “fast” and “slow” in the description above.

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 is prime and is an integer where , then .

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

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

For example, suppose we want to test . Let’s pick . We compute ; hence is not prime (but you probably knew that already). In this particular exampe is actually a factor of , but it need not be. For example, let and pick ; then computing proves that is composite, even though and share no common factors.

So what if is equivalent to ? Unfortunately, Fermat’s Little Theorem is not an “if and only if” statement! It is quite possible to have even when is composite. So if we do get a result of , we simply can’t conclude anything about . For example, with again, if we happened to pick instead of , then we get even though isn’t prime.

So suppose we pick some and get . What can we do? Well, just try another ! If we get for the new , stop and report that is composite. Otherwise, pick another , and so on.

In general, we can iterate some fixed number of times . If we ever find an such that , then we can report that is definitely not prime. Otherwise, if we get through testing different values of and they all yield , then we can report that 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 big enough so that we could know for sure whether is prime? How big would 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!