By Kamal Lodaya, Institute of Mathematical sciences, Chennai

The international scientific community was truly stunned when the New York Times reported on a new discovery from IIT Kanpur.

The alacrity with which the Americans woke up to the discovery along with its far reaching implications in web related technologies surprised many in the US.

On the face of it, the discovery sounds simple: how to find out whether a number is prime or a composite number. This is easy to solve for small numbers but not for very large numbers. Mathematicians from all over the world have been working to solve this for more than a few hundred years. This problem had also haunted theoritical computer scientists.

Now, a truly world-class theoritical computer science achievement has come out from India solving this.

The ``primality'' algorithm of Manindra Agrawal, Neeraj Kayal and Nitin Saxena of IIT Kanpur, released earlier this month, is the answer to these worries.

Given a number, this algorithm checks whether it is composite (can be divided by a smaller number, a ``factor'') or prime (the only smaller number dividing it is 1).

The IIT 'algorithm' works better for large numbers than previous methods. Agrawal is a researcher in his thirties, well known for his work in the theoritical computer science community. Kayal and Saxena are in their twenties, and part of this work was done while they were doing their BTech in computer science.

The primality algorithm just declares a number to be composite but doesn't yield the smaller number dividing it. If the method can be extended to also give a smaller divisor (a ``factorization algorithm''), computer programs will be able to crack security codes---for example---of the kind used in credit cards. So the whole e-commerce industry will have to operate with new security algorithms.

There have been excellent theoritical computer science results by Indians before this, but many of them have been working abroad. One of them, Madhu Sudan of MIT, has just been awarded the Nevanlinna prize, a top award in theoritical computer science presented at the International Congress of Mathematicians (recently held in Beijing).

One of the many results he obtained was a better algorithm for checking, given a mathematical proof, whether it is correct or not. The algorithm, developed with four other authors, works most of the time but has a small probability of failure. This means that by running the same program several times, the chances of a mistake become lower.

An algorithm of this kind was developed for the primality problem by Michael Rabin many years ago, and the importance of the IIT Kanpur result is that it always works, with no chance of failure