Tags

,

Manindra Agrawal, Neeraj Kayal, Nitin Saxena.

These are the names associated with an achievement India never celebrated. This achievement happened in 2002. In a country obsessed with Cricket and Bollywood (or all things foolish), this stupendous and enormously important achievement didn’t matter and went into quick oblivion, though I doubt if it ever came into limelight. The achievement in question is AKS Primality Test (Agrawal-Kayal-Sexena Primality Test). This is named after three minds behind this achievement. If you try to search ‘AKS Primality Test’ on Google, the first two pages of results doesn’t contain any ‘indian’ link. Ok, only one result and that too from their alma mater Indian Institute Technology website, Kanpur. At the time they published their results, Manindra was professor of Computer Science at IIT Kanpur, while Neeraj and Nitin were his doctoral students.

index

AKS Primality Test: In the most basic sense, this test can be implemented to check if any general number is prime. This test runs in polynomial time and is general, deterministic & non-conditional. All other earlier algorithms didn’t have at least one of the above attributes. Apart from this, their algorithm was way too easy to understand. As Folkmar Bornemann has put it; this test is surprisingly elegant and brilliantly simple. The title of their paper was: Primes is in P. (The question is said to be in class P if some algorithm can solve it in polynomial time. Similarly, a question is in class NP if an answer to this can be verified in polynomial time. P vs NP problem is one of the most important unresolved problem in computer science.)

As such, it is understandable why their feat wasn’t celebrated. To celebrate this feat, you have to first understand what you are celebrating. You have to appreciate what they’ve done. The fact is there are far too less people (me included) who could understand it. In a country, where most of the engineers can’t even differentiate computer science with computer engineering, it is understandable why it wasn’t appreciated in the first place. But the problem they solved is not merely a mathematical problem. The problem they solved have very strong ramifications for cryptography and e-commerce. Even from the point of view of mathematics, this was a giant feat. After all, study of prime numbers has always been at the heart of mathematics. Riemann Hypothesis, which is considered to be one of the toughest and most important problem is about prime numbers. Though they solved it from the point of view of computer science and there solution was basically an algorithm, it created wild excitement in mathematical world also. One mathematician, after hearing about this result, said this was the best result he had seen in last ten years. In fact mathematician P. Leyland said, “One reason for the excitement with in the community is not only does this algorithm settle a long-standing problem, it also does so in a brilliantly simple manner. Everyone is now wondering what else has been similarly overlooked.” The algorithm was too simple to be believed. In fact, almost every article or blog on web has something to say about its simplicity. Now mathematicians are asking how many simple solutions to difficult problems are similarly overlooked. They couldn’t believe thousands of mathematicians had been unable to find such an simple algorithm in more than two thousand years.For their seminal work, they were awarded Godel Prize along with Fulkerson Prize along with numerous other awards. Manindra Agrawal went on to win Infosys Prize in 2008. He was the first recipient of Infosys Prize.

As of now, Manindra Agrawal  is professor at IIT Kanpur, Neeraj Kayal is at Microsoft as research scientist and Nitin Saxena is a professor at Hausdorff Center for Mathematics, Germany. I’ve never met or seen them. I don’t understand their work on mathematical level. Still, I have a deep sense of respect for them. They should have been treated as national heroes which they weren’t.

Advertisements