Theorem12.3.1The Square Root of Fermat's Little Theorem
\begin{equation*}a^{(p-1)/2}\equiv \pm 1\text{ (mod }p)\text{ for any odd prime modulus }p\nmid a\end{equation*}
Section12.3Another Primality Test¶ permalink
For a long time it was open whether we might be lucky and there are finitely many Carmichael numbers. However, as was proved in the mid-nineties, there are infinitely many Carmichael numbers.
So now what? Can we find other ways to reliably get primes?
Subsection12.3.1Another pattern
To answer this, we turn to another result visible in our modular power graphic.
As usual, Fermat's Little Theorem is the right-hand column. What's that pattern in the middle column?
What is the use for us of this theorem? Think similarly to the pseudoprime situation. Imagine we are testing some number \(n\) for primality, but we then find that \begin{equation*}a^{(n-1)/2}\not\equiv \pm 1\text{ (mod }n)\; ,\end{equation*} then that number is definitely not prime.
Let's try this on our pesky Carmichael number, once again starting with base \(a=2\).
Not again! Try another base – maybe \(a=3\)?
Phew, this works, as \(3^{(561-1)/2}\not\equiv \pm 1\) (and \(561\) is not prime). So this criterion does help us test at least a little better.
Subsection12.3.2Miller's test
A slightly stronger variant of this test is called Miller's test base \(a\) for primality.
Algorithm12.3.2Miller's test for base \(a\)
We will proceed by dividing and then checking a congruence.
Begin with taking \(n-1\); divide it by two, and then check the power \begin{equation*}a^{(n-1)/2}\text{ (mod }n)\end{equation*} If the result is \(-1\) we say \(n\) passes Miller's test. If the result is not \(\pm 1\), we say it fails Miller's test (since if \(n\) is prime, the result would certainly be \(\pm 1\)). If the result is \(+1\), we continue.
Assuming \(a^{(n-1)/2}\equiv 1\), we continue by dividing the power itself by two and then taking \(a\) to that new power. Once again, if the result is \(-1\) we say \(n\) passes the test, and if it is not \(\pm 1\), we say it fails.
If the result is \(+1\), continue dividing the power by two, check the result. If we arrive at the point where we have divided \(n-1\) by all possible powers of two and the result is still \(\pm 1\), then we say \(n\) passes the test.
Example12.3.3
Let's see a few examples of this. First, here is a number pseudoprime base 2 – but it does not pass this test, which is good since it's composite.
Looking good … But let's try another pseudoprime number (a Mersenne number, in fact) to see if it passes, just to be sure.
As we can see, this shows that \(n=2047\) passes the first part of Miller's test base 2, and that there is no further to go because \((2047-1)/2=1023\) is odd. So, as far as we know thus far, \(2047\) is prime.
Let's try this same test with an actual prime.
We see that this passes Miller's test the first time, but we keep going since we got \(\equiv 1\); the second time we got \(\equiv -1\), so we stop and hope it's prime. (It is, in this case!)