Section12.4Strong Pseudoprimes

Since composite numbers can pass this primality test too, this can get frustrating if we don't organize. So we come up with another name.

Definition12.4.1

We call a composite number \(n\) that passes Miller's test base \(a\) a strong pseudoprime base \(a\).

The bad news is that strong pseudoprimes exist, as we saw above with \(n=2047\). In fact, we can prove a theorem about it.

Theorem12.4.2

If \(n\) is a pseudoprime base \(2\), then \(2^n-1\) is a strong pseudoprime base \(2\).

Proof

Corollary12.4.3

Since \((\pm 1)^2=1\), we have proved that if \(n\) is a pseudoprime base \(a\), so is \(2^n-1\).

Corollary12.4.4

There are infinitely many strong pseudoprimes (and hence regular pseudoprimes) base 2. (Just keep doing \(2^n-1\).)

For instance, we now know that \(2^{341}-1\) must fall in that category, and since the second number below is odd, this confirms it.

Subsection12.4.1Probabilistic Primality

BUT there are not strong Carmichael numbers! In fact:

Theorem12.4.5

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\).

The proof of this is doable for us. It counts numbers of solutions of \(x^\ell-1\) modulo various prime powers and combines them with the CRT to give a good counting argument. It is long enough to omit at this time, though.

Needless to say, no one could compute that many bases to prove primality! But 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\); simply run Miller's test for \(k\) different bases less than \(n-1\), and if a number passes all of them, that is the probability.

For 100 primes, this is the probability that would come out.

So if you run the test for 100 primes, 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.