Section12.2Primes — Probably
Primality testing is full of little tidbits like this, 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 the course).
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 you use enough tests that do not guarantee primality but have a quite low false positive rate in practice, then the number you have is more likely to be a prime than the chance that your computer made an arithmetic error.
This is astonishing, but true; and if you end up with a number that likely to be prime, you can always check it with one of the various slower tests I will not describe.
Subsection12.2.1Pseudoprimes
We start this discussion with our visual representation of powers. Notice again here that Fermat's Little Theorem is visible in the second-to-last column.
The last column is a slight restatement of Fermat's Little Theorem. It turns out that of course if \(a\equiv 0\) mod (\(p\)) then \(a^{p-1}\) can't be \(1\), but no matter what \(a\) is, it is always true that \[a^p\equiv a\text{ mod }(p)\, .\]
This is useful, as it works for all primes. We can now use it to state a test for possible primality:
So if \(a^n\equiv a\) mod (\(n\)) for a given \(n\), it's at least possible that \(n\) is prime.
Definition12.2.2
If \(a^n\equiv a\) mod (\(n\)), we say \(n\) passes the base\(a\)test.Definition12.2.3
If \(a^n\equiv a\) mod (\(n\)) but \(n\) is not prime, we say it is a pseudoprime base \(a\).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.
It turns out that everyone from the ancient Chinese (e.g. the times of Master Sun from the CRT) to Leibniz used this test for the base \(a=2\) to assert numbers are prime. And it doesn't do a bad job. It's sort of like internet date matching for primes!
We can change the numbers in the range above to check for more -- say up to 1000. Are there any that satisfy this test and are not prime?
To the surprise of many in the world of numbers, \(n=341\), \(n=561\), and \(n=645\) turn out to fall in that category!
That's still not bad -- out of 171 total such potential pseudoprimes base 2, only 3 of them actually are not prime, or about one and three quarters percent!
Perhaps unfortunately to cryptographers (though interestingly to pure mathematicians!), it turns out that there are infinitely many such pseudoprimes:
Fact12.2.4
If \(n\) is a pseudoprime (base 2), then so is \(2^n-1\).We will get this as a corollary of something stronger below. All the Fermat and Mersenne numbers pass this test, incidentally, though they are all quite large compared to a typical number you might try.
Subsection12.2.2Prime impostors, and how to avoid them
If we want to check things out more carefully, of course, we can try to test for primality with a different base.
As you can see, this exposes 341 and 645 as fakes. What about 561? Let's try with base 5 as well.
Hmm, that's interesting. What if I add some primes, like 7 or 11? Try it above.
In the next cell, I get systematic. We should expect output if \(561\) doesn't pass the test.
It appears that \(p^{561}\equiv p\) mod 561 for every prime \(p\)! This can in fact be proved.
Fact12.2.5
The number \(561\) is a pseudoprime for every prime base \(p\).Proof
Definition12.2.6
We call a number which is pseudoprime to every base but not prime a Carmichael number, in honor of the first person to actually produce such numbers in 1912, Robert Carmichael.So is \(561\) a Carmichael number?
This example suggests that to find a Carmichael number, 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\). It turns out that this is true -- in fact, we can prove something even more accurate.
Proposition12.2.7Korselt's Theorem
Carmichael numbers are precisely those composite \(n\) for which \(n\) is a product of all distinct primes \(p_i\) (no squares) \[n=p_1p_2p_3\cdots p_k\text{ with }p_i\neq p_j\] such that \[p_i-1\mid n-1\] for all the prime factors.Certainly prime numbers satisfy this trivially! In this case, 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 that is the entire proof that such numbers are Carmichael numbers.
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\).