THREE computer scientists have shocked the mathematics community by finding a solution to the centuries-old problem of how to tell if a number is prime. The proof is striking in its simplicity, and has mathematicians wondering what else they may have overlooked.
Prime numbers, which are divisible only by themselves and 1, are fundamental building blocks of mathematics and have fascinated scholars since ancient times. In 240 BC the Greek mathematician Eratosthenes came up with the first foolproof way of telling if a number is prime. But the time the method takes increases exponentially with the size of the number, so for very long numbers you’d need longer than the age of the Universe to solve the problem. Since then mathematicians have been trying to find a “polynomial-time” algorithm, which gives an answer in a reasonable amount of time.
The search has intensified over the past few decades, since prime numbers have become vital for cryptography. The encryption system used to secure Internet transactions relies on the fact that finding prime factors of large numbers is extremely difficult. The algorithms currently used to help find these factors are fast, but they only give a probability for whether a number is prime or not. Though the probability can be very high, these algorithms don’t constitute a proof.
Advertisement
Now Manindra Agrawal and his undergraduate students Neeraj Kayal and Nitin Saxtena have succeeded where the best minds in mathematics have failed. The trio, based at the Department of Computer Science and Engineering at the Indian Institute of Technology in Kanpur have devised an algorithm that gives a definite answer to the problem in a reasonable time.
Their success lies in the fresh approach they took to the problem. Instead of asking the one big question “is this number prime?”, they generate a whole series of smaller questions or “equalities” from the number being tested. “If the equalities hold then the number is prime, if any one of them doesn’t hold then the number is not prime,” explains Agrawal.
So far thousands of mathematicians have worked through the proof currently posted on the institute’s website (). “Those that have emailed me have all appreciated the algorithm and said that it’s correct,” Agrawal told 91av.
Experts had suspected a polynomial-time algorithm was possible. But they didn’t foresee the sheer simplicity of the 13-line solution that Agrawal and his colleagues present (see below). “It’s a beautiful solution and I’m very happy for them, but I’m a little embarrassed that I didn’t see it myself,” says prime number expert Carl Pomerance of Lucent’s Bell Labs in New Jersey. “Their solution is simple. That’s not to say it’s trivial, what they’ve done is very clever,” he adds.
The theoretical advance is significant in its own right, but Ian Stewart of Warwick University says the method should also help mathematicians solve other problems where they have reached a dead-end using other techniques.
Internet security is not yet under threat. “The solution is likely to have very little impact,” says Ben Hadley of nCipher, a cryptography security company based in Cambridge, because it offers no real advantage over the probabilistic algorithms already used in the industry. But Pomerance believes the existence of the proof will still have cryptologists worried. “If there’s a simple test for primality, there may well be a simple way to determine prime factors that we’re currently overlooking,” he says.
This is the real significance of the trio’s work. The fact that undergraduates working on their final-year project can solve such a long-standing riddle raises the possibility that other simple solutions to big mathematical problems may have been missed. “It is a reminder of how we can overlook the simple things,” says Pomerance.
