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.

The bad news is that strong pseudoprimes exist, as we saw above with \(n=2047\). In fact, we can prove a theorem about it, which is analogous to Fact 12.2.5 and has it as an implication.

But there are not strong Carmichael numbers! In fact:

Needless to say, no one could compute that many bases to prove primality for any realistic \(n\)! 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\).

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.