Last night on the plane ride home I was reading a copy of Dr. Dobb’s Journal, a magazine for programmers (I think I got a free subscription to this when I registered for PHPCon). I came across Michael Swaine’s column and read about a polynomial-time algorithm for testing primes that was discovered this summer.
I know this is old news (blogs are supposed to be up-to-the-minute, right?) but it’s still totally fascinating for anyone who understands how public-key cryptography works (I learned about it in Math 42 at Brown).
Although this algorithm is considered super-fast for what it does, it is actually slower than the ones used by RSA and PGP when generating new public/private key pairs. The difference is that this new algorithm has the distinct advantage of telling you definitively whether or not a number is prime. The more common apporach is to run a probabilistic algorithm so that there still exists a possibility that the number you’re evaluating is not prime, but it’s more likely that you’ll be struck by lightning. Although the traditional probablistic approach is still faster than this new technique, it doesn’t give you the 100% confidence that some people (bankers?) would rather have.
From a practical standpoint, 99.99999999999999% confidence ought to be enough for anyone, because insurance policies aren’t that expensive when you’re talking about covering something that has a 0.00000000000001% likelihood of happening.
But from a theorhetical computer science standpoint, this discovery is just plain cool. If they could only prove that P != NP, I’d be really psyched.