Matthew van Eerde's web log
I am a Software Development Engineer in Test working for the Windows Sound team. You can contact me via email: mateer at microsoft dot com
This morning my wife (whom I love and adore) woke me up at 3:00 AM with an urgent question.
"Hey!" she said, shaking me awake.
"Is 19 prime?"
Like a fool, I answered her. "Yes. Yes it is." Off she went.
This is a true response, but not a correct response. I realized shortly afterwards that a correct response would look more like:
I'm glad you asked me that. dear. Eratosthenes, the Greek mathematician, discovered a very efficient way to list primes in about 200 BC that is still in use today. You start by writing out all the numbers from 1 to 19: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19. 1 is a very special number (it's the multiplicative identity, or what algebraists would call a unit) so we put a square around it. The first number we didn't consider was 2, so we circle it - that means it's prime - and then cross out every multiple of 2 after that. Going back, the first number we didn't consider was 3... and so on until we get 1 2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19. A common optimization is to realize that after circling a prime p, the first number you cross out (that wasn't crossed out before) is always p2, which means that after circling a number you can immediately jump to its square, and also means you can stop crossing out altogether once you hit p2 > N...
This would allow her to fish rather than waking me up when she wanted a fish.
An even better response would have been:
It's funny you've asked me that. Number theorists and cryptanalysts have considered this question for thousands of years. Eratosthenes' method (see above) is a very simple way to find all the primes below a given number, but an efficient way to determine whether a given number is prime was found only very recently.
In practice, the test that is usually used is the randomized version of the Miller-Rabin test. Although this is nondeterministic, it is very fast indeed, and will tell you to a very high degree of certainty whether the given number is prime. This usually suffices.
There is a deterministic version of the Miller-Rabin test too, which is guaranteed to tell you with perfect certainty whether the given number is prime. But it only works if you believe in the generalized Riemann hypothesis. Most mathematicians nowadays believe the hypothesis, but no-one has (yet) been able to prove it.
Amazingly, in 2002 three mathematicians named Manindra Agrawal, Neeraj Kayal, and Nitin Saxena came up with a deterministic, proven, polynomial-time (specifically, polynomial in the number of digits in the input) method for telling whether a given number is prime. This is known as the AKS primality test. The most striking thing about this test is its simplicity - if something this straightforward can be found after thousands of years of looking, what else out there remains to be found?
Such a response would probably prevent her from waking me again for any mathematical problem at all. Boo-ya.
Here's Agrawal, Kayal, and Saxena's "PRIMES is in P" paper.
Here's Yves Gallot's C++ implementation of AKS.
My own Perl implementation follows:
Here's the output when I run it on 19:
And here's the output with a bigger input: