Definition 12.4.1.
We call a composite number \(n\) that passes Miller’s test base \(a\) a strong pseudoprime base \(a\).
Section 12.4 Strong Pseudoprimes
Since composite numbers can pass Miller’s test too, nomenclature can get frustrating if we don’t organize. So we come up with another name.
The bad news is that strong pseudoprimes exist, as we saw above with \(n=2047\text{.}\) In fact, we can prove a theorem about them analogous to Fact 12.2.7, and which implies it (see Corollary 12.4.3).
Theorem 12.4.2.
If \(n\) is a pseudoprime base \(2\text{,}\) then \(2^n-1\) is a strong pseudoprime base \(2\text{.}\)
Proof.
As per our convention, let \(n\) be composite and odd, but it passes the base two test:
\begin{equation*}
2^{n}\equiv 2\text{ (mod }n)\text{.}
\end{equation*}
Since \(n\) is odd, we can cancel \(2\) in the congruence, and get
\begin{equation*}
2^{n-1}\equiv 1\text{ (mod }n)\text{.}
\end{equation*}
Rewrite this as \(2^{n-1}-1=nk\) for some integer \(k\text{.}\)
Since \(2^{n-1}-1\) is odd, then so is \(k\) necessarily. Now comes some final manipulation to prepare to apply Miller’s test to \(2^n-1\text{:}\)
\begin{equation*}
\left(2^{n}-1\right)-1=2^n-2 =2\left(2^{n-1}-1\right)=2nk\text{.}
\end{equation*}
Now use the preceding equation as the exponent in Miller’s test and a clever reduction:
\begin{equation*}
2^{[(2^n-1)-1]/2}=2^{2nk/2}=2^{nk}=\left(2^n\right)^k\equiv 1^k\equiv 1\text{ (mod }2^n-1)\text{.}
\end{equation*}
Since \([(2^n-1)-1]/2=2^{n-1}-1\) is odd, the number passes Miller’s test.
All that remains is to show \(2^n-1\) is composite if \(n\) is composite; this is a fairly straightforward extension of Lemma 12.1.2 (see Exercise 12.7.7).
Corollary 12.4.3.
Proof.
All we need is that \((\pm 1)^2=1\text{.}\)
Corollary 12.4.4.
There are infinitely many strong pseudoprimes (and hence pseudoprimes) base 2.
Proof.
Take your favorite pseudoprime, and keep subtracting one from two to the power of the previous (strong) pseudoprime.
Example 12.4.5.
For instance, we now know that \(2^{341}-1\) must fall in that category. If you try the cell below you will see that the (very large) second number is odd, which confirms it.
But there are not any ‘strong Carmichael numbers’! In fact:
Theorem 12.4.6.
If \(n\) is an odd composite positive integer, then \(n\) passes Miller’s test for at most \((n-1)/4\) bases \(a\) between 1 and \(n-1\text{.}\)
Although the proof is accessible to us at this point, we will not provide it for the sake of space. It counts numbers of solutions of \(x^\ell-1\) modulo various prime powers and combines them with the Chinese Remainder Theorem to give a good counting argument.
Needless to say, no one could use the base \(a\) test for enough bases to prove primality for any realistic \(n\text{!}\) But Michael Rabin used this fact to suggest a test for a probable prime with probability of failure less than \(\left(\frac{1}{4}\right)^k\) for any desired \(k\text{.}\)
Algorithm 12.4.7. Miller-Rabin (probabilistic) primality test.
Run Miller’s test for \(k\) different bases less than \(n-1\text{.}\) If a number passes all of them, the probability of failure is less than \(\left(\frac{1}{4}\right)^k\text{.}\)
For 100 bases, this is the probability that would come out.
So if you run the test for 100 bases, you are in pretty decent shape.
You can also always use some slow test to prove primality. That is what is called a certificate of primality, and although you may not believe it, programs that reliably generate reasonably large (100-200 digits, right now) primes and can verify it are hot items on the virtual shelves of those who care about such things.
Finally, let’s see this in action. Remember that we wanted keys larger than 1024 bits for at least a semblance of security in RSA? Here we go with a start:
The \(p\) and \(q\) we get above are just probable primes. Verifying them could take a little longer! Here, we try it with just one of them.
Sage note 12.4.8. Reminder about timing.
Don’t forget, you could use
%time is_prime(p) to time this operation in a worksheet or Sage command line.
