Prime achievement

100 per cent accurate computer algorithm to identify prime numbers

Published: Sunday 15 December 2002

A team of scientists has developed a solution for an ancient and important problem -- how to find out whether a number is a prime or not. Manindra Agrawal with his students Neeraj Kayal and Nitin Saxena from the Indian Institute of Technology (IIT), Kanpur, have come up with a computer algorithm that solves the ancient problem. It would take the algorithm just a few seconds to identify, for instance, whether 2498765457891 is a prime number or not. The algorithm is unique because it is 100 per cent accurate -- something that has not been achieved before. Prime numbers are divisible only by themselves and the number one. They are extremely valuable in computer sciences and mathematics. For example, encryption of information transferred over the Internet is achieved in 'packages' of very large semi-prime numbers (which are divisible only by two prime numbers). These packages are known as RSA numbers, and unless the receiver knows which prime numbers are used to make the RSA number, they will not be able to decode the information.

"Any developments in terms of determining primes or calculating primes, will have implications for cryptography because the basis of this technique is identifying massive prime numbers," says Eric Allender, a professor of computer science at the State University of New Jersey at Rutgers, usa.

Existing computer programmes are able to estimate prime numbers, but they carry a small degree of inaccuracy. However, they are much faster than the new algorithm as they have fewer steps. The IIT researchers say that their next challenge will be to reduce the number of steps of the algorithm.

Subscribe to Weekly Newsletter :

Comments are moderated and will be published only after the site moderator’s approval. Please use a genuine email ID and provide your name. Selected comments may also be used in the ‘Letters’ section of the Down To Earth print edition.