Skip to main content

Section 12.2 Primes – Probably

Primality testing is full of little tidbits like those in the previous section, and tantalizingly devoid of easy methods that work for all special cases. Indeed, none of these paths lead us to reliable, reasonably fast discovery of large primes for cryptographic purposes, nor do other computationally infeasible methods like using Wilson's Theorem or other even stranger formulas (some of which appear later in this text).

Instead, what is typically done is to pick a number, and then use tests on it that do not guarantee primality!

Why would this work? The idea is that if a given number passes enough tests that do not guarantee primality but have a quite low false positive rate in practice, then the probability the number you have is composite is lower than the (very low) chance that your computer made an arithmetic error due to cosmic rays (though one still has to be careful of bugs like the one described in the discussion before Algorithm 12.1.9).

This is astonishing, but true. Then if you end up with a number that likely to be prime, you can always confirm its primality with one of the various slower tests I will not describe.

Subsection 12.2.1 Pseudoprimes

We start this discussion with our visual representation of powers (see Subsection 8.2.1).

Colored table of powers modulo \(n=11\)
Figure 12.2.1. Colored table of powers modulo \(n=11\)

Notice again here that Fermat's Little Theorem is visible in the second-to-last column. The graphic has been expanded, so that the last column is a slight restatement thereof, true for all \(a\text{:}\)

\begin{equation*} a^p\equiv a\text{ (mod }p)\text{.} \end{equation*}

(See Exercise 12.7.3 and Exercise 9.6.3.) Go ahead and confirm it in the interactive version.

This is a useful criterion, as it works for all input, including multiples of the modulus. We can now use it to state a test for possible primality:

So if \(a^n\equiv a\) (mod \(n\)) for a given \(n\text{,}\) it's at least possible that \(n\) is prime.

Definition 12.2.3.

If \(a^n\equiv a\) (mod \(n\)), we say \(n\) passes the base \(a\) test.

It turns out that everyone from the ancient Chinese to Leibniz used this test for the base \(a=2\) to assert numbers are prime. And it doesn't do a bad job. As some former students pointed out, it's sort of like internet date matching for primes; it doesn't always work but can succeed reasonably often.

We can change the numbers in the range of the preceding interact to check for more – say up to 1000, which allows exploring the following question.

Question 12.2.4.

Are there any numbers which satisfy the base \(a\) test and are not prime?

To the surprise of many in the world of numbers, the answer is yes. The numbers \(n=341\text{,}\) \(n=561\text{,}\) and \(n=645\) turn out to fall in that category (for base \(a=2\)).

That's still not bad – out of one hundred seventy-one total such potential primes base \(2\text{,}\) only three of them actually are not prime, or about one and three quarters percent. That is unusual enough that we have a special name for composite numbers that pass one of the base \(a\) tests.

Definition 12.2.5. Pseudoprimes.

If \(a^n\equiv a\) (mod \(n\)) but \(n\) is not prime, we say it is a pseudoprime base \(a\text{.}\)

That is to say, if a number satisfies Fermat's Little Theorem, we think it is likely enough to be prime to call it a pseudoprime if it isn't. (Prime, that is.)

Remark 12.2.6.

We will loosely follow a somewhat standard convention, particularly since we're talking about finding primes, and only consider odd pseudoprimes. In fact, according to an article by some experts in pseudoprimes [E.7.32], the first even pseudoprime to the base \(2\) (\(161038=2\cdot 73\cdot 1103\)) was only discovered in 1950. See also Exercise 12.7.16.

Perhaps unfortunately to cryptographers (though interestingly to pure mathematicians!), it turns out that there are infinitely many such pseudoprimes.

We will get this result as a corollary of something stronger soon (see Corollary 12.4.3 and Theorem 12.4.2).

All the Fermat and Mersenne numbers pass the base \(2\) test, incidentally, though they are all quite large compared to a typical number you might try.

Subsection 12.2.2 Prime impostors, and how to avoid them

If we want to check things out more carefully, we can try to test for primality with a different base. In the next cell, we choose \(a=3\text{.}\)

As you can see, this exposes \(341\) and \(645\) as fakes. What about \(561\text{?}\) Let's try that one with base \(a=5\) as well.

Hmm, that's interesting. What if I change to a different prime base, like \(a=7\) or \(11\text{?}\) Try it above.

In the next cell, I get systematic. We should expect output if \(561\) doesn't pass the base \(a\) test for some \(a\text{.}\)

It appears that \(p^{561}\equiv p\) mod 561 for every prime \(p\text{!}\) Let's prove it.

We know that

\begin{equation*} 561=3\cdot 11\cdot 17\text{,} \end{equation*}

so by Fact 7.2.2 (and, ultimately, the Chinese Remainder Theorem)

\begin{equation*} a^{561}\equiv a\text{ (mod }561) \end{equation*}

if and only if \(a^{561}\equiv a\) holds for the prime power factors \(3,11,17\text{;}\) so we will check them.

Remember, the exponents for these congruences live in the (mod \(\phi(p)\)) world, so we just need to check what \(561\) is in each of those worlds. We get:

  • \(561\equiv 1\text{ (mod }16=17-1)\) so \(a^{561}\equiv a^1\text{ (mod }17)\)

  • \(561\equiv 1\text{ (mod }2=3-1)\) so \(a^{561}\equiv a^1\text{ (mod }3)\)

  • \(561\equiv 1\text{ (mod }10=11-1)\) so \(a^{561}\equiv a^1\text{ (mod }11)\)

That is, for \(p=3,11,17\) we see

\begin{equation*} a^{561}\equiv a^{1}\text{ (mod }p) \end{equation*}

Using Proposition 5.4.5, this congruence is always true!

By the way, we note that \(a^{560}\) is not congruent to \(1\text{,}\) which explains why we use \(a^n\equiv a\) for these definitions.

Definition 12.2.9.

We call a number which is pseudoprime to every base \(a\text{,}\) but is not a prime number a Carmichael number, in honor of the first person to actually produce such numbers, Robert Carmichael (in 1912).

So is \(561\) a Carmichael number? We saw the factorization above, but here it is again:

The proof of Fact 12.2.8 suggests that to find a Carmichael number \(n\text{,}\) we might want to look at \(n\) which are a product of primes \(p_i\) such that \(n-1\equiv 1\) in the exponent world of \(p_i\text{.}\) It turns out that this is true, and one can prove something even more specific.

Prime numbers satisfy almost all the conditions trivially. To show that \(561\) is a Carmichael number we used this idea in the form \(n\equiv 1\) (mod \(\phi(p_i)\)) for all three prime factors, and essentially the same argument applied to any number satisfying the hypotheses is a Carmichael number.

We will not prove the other half of this theorem (that all Carmichael numbers have this form). It is not hard, however, using a slight variant on the Euler \(\phi\) function one can acquire from investigating \(U_n\) for composite \(n\text{.}\)

Example 12.2.11.

Evaluate this Sage cell to see the previous result applied to identify another Carmichael number.