Indian Discovery Stuns Scientific Community

[Guest guest]

Special: IIT 'algorithm' creates ripples in the US

By K Venkatesh

 

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