Monte Carlo Primality Testing

I’m going to take a stab at proposing a Monte Carlo algorithm for primality testing that will take a trivial amount of time. It’ll turn out to be a terrible algorithm in practice, so don’t try it at home! In fact, I’m going to call this method “Bad Primality Testing.” I’m only introducing it because it’ll make the “good” primality testing easier to understand.

Here is the Bad Primality Testing algorithm:

Instead of dividing number by all odd integers from 3 and up until the square root of number, we’ll divide number by a bunch of randomly chosen integers. If we choose, say, 100 random integers and divide number by them and always get a remainder, there’s a certain probability that number is prime.

This certainly qualifies as a Monte Carlo algorithm. It has a guaranteed speed, as we perform a fixed number of 100 division operations. However, it only has a certain likelihood of being correct.

The problem with Bad Primality Testing, though, is that it’s not reliable enough. For example, many composite numbers have only one pair of smaller numbers that multiply into that composite number. Indeed, this is what happens when the smaller numbers are themselves both prime. So, if we test a number like this, it’s likely that none of our 100 random divisions will divide our number by either of those smaller numbers that compose our number. And so, the odds are high that we’ll mistakenly identify our number as prime when it’s composite.

If our Monte Carlo algorithm will likely be wrong for certain numbers, it’s a pretty poor algorithm. Monte Carlo algorithms are valuable when the odds are that they’ll be correct, even if there’s no guarantee. But if the odds are in favor of getting the wrong answer, we’d better avoid such an approach.