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鈥檇 need longer than the age of the Universe to solve the problem. Since then mathematicians have been trying to find a 鈥減olynomial-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鈥檛 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 鈥渋s this number prime?鈥�, they generate a whole series of smaller questions or 鈥渆qualities鈥� from the number being tested. 鈥淚f the equalities hold then the number is prime, if any one of them doesn鈥檛 hold then the number is not prime,鈥� explains Agrawal.
So far thousands of mathematicians have worked through the proof currently posted on the institute鈥檚 website (). 鈥淭hose that have emailed me have all appreciated the algorithm and said that it鈥檚 correct,鈥� Agrawal told 快猫短视频.
Experts had suspected a polynomial-time algorithm was possible. But they didn鈥檛 foresee the sheer simplicity of the 13-line solution that Agrawal and his colleagues present (see below). 鈥淚t鈥檚 a beautiful solution and I鈥檓 very happy for them, but I鈥檓 a little embarrassed that I didn鈥檛 see it myself,鈥� says prime number expert Carl Pomerance of Lucent鈥檚 Bell Labs in New Jersey. 鈥淭heir solution is simple. That鈥檚 not to say it鈥檚 trivial, what they鈥檝e 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. 鈥淭he 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. 鈥淚f there鈥檚 a simple test for primality, there may well be a simple way to determine prime factors that we鈥檙e currently overlooking,鈥� he says.
This is the real significance of the trio鈥檚 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. 鈥淚t is a reminder of how we can overlook the simple things,鈥� says Pomerance.