The Fermat primality test and the GCD test

In my previous post we proved that if $a$ shares a nontrivial common factor with $n$ , then $a^{n-1} \not\equiv 1 \pmod n$ , and this in turn proves that $n$ is not prime (by Fermat’s Little Theorem).

But wait a minute, this is silly: if $a$ shares a common factor with $n$ , then we don’t need anything as complex as Fermat’s Little Theorem to figure out that $n$ is not prime! All we have to do is compute $\gcd(a,n)$ using the Euclidean Algorithm, and when we find out that the result isn’t $1$ , we can immediately conclude that $n$ isn’t prime since it has a nontrivial divisor.

So for comparison, let’s consider this (terrible!) primality test, call it the GCD test: given an $n$ we want to test, pick values of $a$ such that $1 < a < n$ and compute $\gcd(a,n)$ for each one. If we find an $a$ for which $\gcd(a,n) \neq 1$ , then $n$ is not prime.

This is terrible for several reasons. First, if we want this test to tell us for certain when $n$ is prime, we essentially have to try all the possible values of $a$ . We can optimize a bit by only trying $1 < a \leq \sqrt{n}$ —if $n$ has any nontrivial divisors we will be sure to find some that are under $\sqrt{n}$ —but this doesn’t help all that much in the grand scheme of things. In fact, this GCD test is actually almost the same thing as trial division, where we try a bunch of different numbers to see whether they evenly divide $n$ . Both are essentially trying to find divisors of $n$ by brute-force search.

So suppose instead that we are willing to live with some uncertainty, and we just try some fixed number of values for $a$ , and either conclude with certainty that $n$ is composite (if we happen to find an $a$ that shares a nontrivial factor with $n$ ), or report that it is probably prime. How bad can this be—or put another way, how many values of $a$ do we have to try so we can be “reasonably certain” that $n$ really is prime when the test says it is?

The answer is that it can be very bad indeed. Euler’s totient function $\varphi(n)$ counts the number of integers $\leq n$ which are relatively prime to $n$ . So if $n$ is composite and we pick $1 < a < n$ uniformly at random, there are $\varphi(n)$ choices which won’t reveal the fact that $n$ is composite, and approximately $n - \varphi(n)$ choices which do share a common factor with $n$ and hence do reveal the fact that it is composite.

So the question is, how big can $\varphi(n)$ be, relative to $n$ ? We would like it to be small—which would leave us with many opportunities to learn that $n$ is composite—but in fact it can be quite big. For example, $\varphi(961) = \varphi(31^2) = 31\cdot 30 = 930$ , which is not much smaller than $961$ itself. This means that $930$ of the numbers less than $961$ share no factors in common with $961$ ; only $31$ of them share a factor. In fact, $\varphi(n)$ is big precisely when $n$ has just a few large prime factors, which intuitively is exactly when $n$ is most difficult to factor. For such $n$ there really is no acceptable number of $a$ ’s we can test with the GCD test in order to be reasonably sure that $n$ is prime—in the case of $961$ , for example, each $a$ we randomly pick has only a $31 / 961 \approx 3\%$ chance of sharing a common factor with $n$ ; and this can get arbitrarily bad as $n$ gets larger.

So remember we started down this path by showing that if we use the Fermat primality test, values of $a$ which share a common factor with $n$ will definitely reveal the compositeness of $n$ . But now we know that if we rely on only such values of $a$ , not only do we have a very small chance of discovering composite $n$ —no better than just using trial division—but more than that, actually using the Fermat test itself would be silly, since we should just use the simpler GCD test instead!

So if the Fermat primality test is worthwhile at all, it must be because there are other values of $a$ , which don’t share any common factors with $n$ , but nonetheless still reveal the fact that $n$ is composite since $a^{n-1} \not\equiv 1 \pmod n$ . So how many of those values of $a$ are there? Stay tuned!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →