Skip to content
June 1, 2012 / Gyanesh Pandey

Cracking the Primes

(Dr. Manindra Agarwal’s Journey to the Primality Testing)

It was December 2002 when suddenly a rumor spread around in the Computer Science students, who had just graduated from IITK in May that year, that two of their batch mates had completed their PhDs in a matter of few months. It took no time for the mails to be circulated, phone calls to be made, yahoo messengers to ring the message among the students who were either working or were furthering their studies. Two of their own batch mates, friends of many, had completed their PhD and that too How!

When few got the real scoop, the news was even more interesting than the completion of PhD. They had invented an algorithm to solve a huge problem in Mathematics. It had been an open problem for a long time. They had invented an algorithm to test if a number was prime or not. Given the computational ability of Computers, testing if a number is prime or not sounds like a mundane problem. But when the Prime numbers become bigger and bigger, the time taken to test the number for primality increases exponentially – literally!

Like if one was to test, say 5423. A small program can find this out in much less than a second. But what if one was to test 542354235423 was a prime? It would still be a little longer. What if one was to test – (5424)^5 + 1? It takes a long time, so much so that until the advent of Super Computers, there was a limit on the highest Prime Number known. But one may ask, why do you need to find out?

Finding out the largest prime number is not a huge challenge, but to reduce the amount of time taken to test if a number is prime or not, is something that has teased many mathematicians for a long time. As I said earlier, the time taken to test a number would rise exponentially as the number grew larger.

These famous folks had invented an algorithm which took much lesser time and more so as the numbers got bigger, the time did not increase exponentially. It increased in what is mathematically called Polynomial order.

As the rumor would have it – Neeraj Kayal & Nitin Saxena had completed their PhD, having solved this problem. Or more accurately Dr. Manindra Agarwal had agreed to grant them their PhDs, having solved such a remarkable problem.

So, Dr. Manindra Agarwal, Neeraj Kayal & Nitin Saxena had written a paper about their findings and it had instantly caused a storm in the international community.

It was special for all the people sitting in their corporate offices because in last six months they had realized that the intellectual challenges a job offered was not even in the same zone as this effort. Most of the graduates either take up a job or go to US for pursuing further studies. While these people had stuck around here in India to do their PhDs, working with Dr. Manindra Agarwal.

Truth be told, Dr. Manindra Agarwal had been struggling with this problem for a few years now.

Dr. Agarwal has also had a very interesting trajectory like his students Neeraj & Nitin. He graduated from IIT Kanpur in the year 1986. This was the time when there used to be a mass exodus of highly educated and very intelligent engineers or scientists to the rest of the world, read America. The news of various space crafts like Voyager/Challenger was a common news item and the fact that there were a bunch of engineers at NASA which were of Indian Origin, more specifically from IITs was also well known. One of the most common career paths for students graduating from IIT Kanpur was to take the GRE and land up in US to pursue Masters or a Phd.

The problem of brain drain was at such a high that in the same year, the then Prime Minister Mr. Rajiv Gandhi had launched a New Policy of Education. Indira Gandhi National Open University was also started in 1985. There was a new wave as far as educational reforms in India were concerned. It was in the year 1986 that the Indian population living abroad cried their hearts out listening to the song “Chitthi aayi hai, watan se chitthi aayi”. Not that the song could do much more, but crying helps.

Graduating from IIT Kanpur in 1986, Dr. Agarwal decided to stay on India and continue his Phd at IIT Kanpur. Now, he was neither a part of New Policy of Education, nor did he indulge in the sentiment of a Bollywood song but his reason for not going to US was that he could not muster enough courage to study for GRE.

He was an ace student. He had a CPI of 9.3, while the Institute average usually hovers around 7. His All Indian Rank was 38! And he was a Computer Science student. But he could not motivate himself to take the GRE. GRE is a much simpler exam than JEE and lacs of students, all over the world – especially from India – take it every year to go to USA for further studies. The exam involved mugging up virtually the whole English Dictionary. He did start the process but could never motivate himself enough to keep doing it. Thus one of the biggest factors in his staying in IIT Kanpur to continue his Phd was his inability to mug up the dictionary, consequently he did not take the GRE.

His not going to US and continuing to study at IIT K would have much larger implications in his life and around. He enrolled to do his research with Dr. Biswas in the Computer Science department at IIT Kanpur itself.

Not that that is what he wanted to do forever. There were many other tempting options like management, civil services and even other jobs. But, he had never had any inclination towards Management or Civil Services.  Software industry had started functioning in its own accord.  As far as software industry went, he had worked as an intern at a software firm. He had to implement Binary Tree as his assignment there – something which was far from challenging for an IIT Kanpur, Computer Science graduate. That gave him the idea that even a software job is not going to satisfy him – intellectually. So the only option that he had left for him was to pursue further studies and eventually get into research.

Coming from the background that he did, he did not face any music about making such choices. If at all, his parents were only happy that he had decided to stay back in India. Dr. Agarwal has an elder brother who is now settled in United States of America, and his brother has been almost guilty of making that choice. Similarly a distant relative had moved to US and the rest of the family did not necessarily look at it as a great achievement. This was remarkable because typically there is a lot of prize and prestige associated with a son living abroad.

Dr. Agarwal’s parents are retired teachers. His father taught Mathematics at Allahabad University and his mother taught Education there. His parents had never wanted their kids to go to the US – may be because they were from a small town – Allahabad. Allahabad, a small town from certain aspects, is otherwise a place of great importance. Allahabad also used to be a center of education until 90’s, not any more though. Allahabad is perhaps most famous for Prayag – where the rivers Ganga, Jamuna & Saraswati come together. It is considered a great holy destination amongst Hindus.

They lived in a rather congested area called Khuldabad in Allahabad. And the people they dwelt with created no pressures on him to do anything he did not want to do. His childhood was like the childhood of any other North Indian kid – strewn with comics like Champak, Motu-Patlu, Chandamama, Nandan etc. However, he enjoyed mathematics even as a child. Living in the region in which they did, it did not offer him much opportunity for sports. Playing cricket in the lanes was where it ended. He read a lot even as a child – Enid Blyton being one of his early favorites. But he had had an early interest in Mathematics and he pretty much read any book about mathematics he could lay his hands on. However, he would never go and ask someone to get him some book or get a book from the library. He was a shy kid. He was also not particularly studious.

Looking at him one would never guess the activities he was fond of. A typical IIT grad has spent at least XI and XII just sitting on a table and chair – studying. JEE did not allow much room for entertainment. However, some of his favorite activities during those days were to bunk college regularly – go to movies (Amitabh Bachchan being his favorite. Incidentally Mr. Bachchan also hails from Allahabad), sit at a Chai shop and chat with friends, or once in a while visit a nearby girls’ college for some eye tonic. He remembers his benign ogling at girls with a mischievous grin on his face.

One would be surprised because with all this he secured 38th rank in the Joint Entrance Exam for IIT. He surprised many with this result because he studied in Government Inter College, not the best school by any stretch of imagination and there were other better schools like St. Joseph and Boy’s High School in town. He had heard from the friends of his friends that there were some very smart guys in St. Joseph’s Convent, which used to make him nervous. But the result laid his fears to rest and somewhere he felt that it was a fluke.

He continued his studies at IITK with the same indifference but like for many more people, it opened up a whole wide world to a boy, who grew up in a small town in UP. He spent a significant time smoking grass, listening to Pink Floyd and usually cramming up shortly before the exams. Pink Floyd would have never imagined, while they sat composing music in London, that their music would be appreciated so much in this technical Institute, in a small little village called Kalyanpur near a small town Kanpur in Uttar Pradesh. Like in the third of the third of the third world. Grass and Pink Floyd gave a lot of relief to people those days. However, unfortunately the trend was discontinued with US pressuring India to ban Grass. Those days Grass was sold at legal shops like some of those ‘Theka Desi Sharab’ selling local liquor.

Pink Floyd still continues to be so popular in IIT Kanpur and in most other IITs. Somehow people don’t listen to Beatles there, very few to Jethro Tull and then not much of Led Zepplin or other great musical trends but Pink Floyd. It is as if these small little institutes are holding a beacon in this part of the world as a fan following. Dr. Agarwal thinks that they have a certain Indian quality, not very definable, but some deeper connect.

Considering his interest in music, grass and fair bit of indifference to studies, it is funny that he did not have much to do with girls in his college days. IIT Kanpur boasted of one of the most open cultures in the country where boys and girls were permitted in each other’s hostels, without much restriction. He had a reputation.

Once in his third semester – second year, first semester – Dr. Agarwal and some of his friends were busy preparing for their mid-term exams while they lived in the E-Mid wing in Hall 2.

Hostels in IITK are called Halls and each floor in a block is called a wing. So say E Block would have a E-Bot (1st floor), E-mid (2nd Floor) & E-Top (3rd Floor). There are no Ground Floors in IIT Kanpur – they did away with their colonial past!

Now that wing faces the tennis courts. While these guys were busy cramming and getting frustrated, their frustration was fuelled by some M. Tech students playing tennis in the courts, with their girl friends cheering them from the sides. Instantly a bet of 20 rupees was set in their wing – the challenge was to go around the tennis courts in nothing but an underpant. Dr. Agarwal, who was so shy that he would never ask someone to get him a book, thought of this as an interesting proposition. He along with a fellow accomplice went around the court in their underpants.

IITians get more than a fare share of stories of their eccentricities but this one is truly unique. Well the tennis fan-fare stopped then and there. Later that evening the whole girls’ hostel, on the provocation of the gentlemen, landed up outside Hall 2 and demanded the culprits. But IITian males are known to demonstrate unsalable unity against females.

Finally, the issue landed in bureaucratic files, from where even demons don’t emerge.

Dr. Agarwal considers his undergraduate time as a waste of time in which he learnt nothing. And he credits his CPI to having an excellent short-term memory. He would cram up the things just before the exams and then forget all of it very soon. He regrets it.

However, he did graduate with a sense of what he liked and disliked, which is a great achievement because most of us land up living our lives without even wondering about what we really like. Leave aside, one, knowing what one likes and two, acting on it.

And act he did.

After joining under Dr. Biswas as a Phd Student he did get serious about studies and explored not just mathematics. He read up a whole lot of stuff including the Classical Indian Philosophy – Yoga Sutra, Brahma Sutra etc. Now he would hang around with a different set of people. He had now become serious and not just about his vocation – mathematics. He graduated with a Phd in the year 1991.

A lot transpired between 1991 and 1998 – he continued as a research scholar at IIT Kanpur till 93, became a Fellow at School of Mathematics, Madras until 95, Humboldt Fellow in Germany till 96, joined back at IIT Kanpur as an assistant professor in 1996.

It was in the year 1998 when he along with Dr. Biswas, who had also been his Doctoral Advisor, came across an interesting technique for Polynomial Identity Testing. Until then, most of the approaches had used random numbers to do the testing. In this paper that they found, the author used irrational numbers to evaluate an expression, which gave significantly better results. The probability of the result improved with the lesser approximations taken for irrational numbers. However, the problem of Polynomial Identity Testing still remained non-deterministic. But this gave an idea to Dr. Agarwal that he could use this approach to solve some other problem in the field of Complexity Theory, his area of specialization.

In the search of a problem to apply this solution to, he chanced upon the Primality Testing. And it became a haunting problem, as it did not lend itself to his efforts. He felt inside that if increasing the approximation improves the result at some point the problem would become deterministic.

He kept on working on this problem, while the rest of the life continued – classes, home, students and the whole works. About two years later, in 2000, with the help of a student he could prove his approach to be true for numbers as large as 10^9.

It was in the year 2001 that Neeraj & Nitin joined him for their B. Tech project -their final year of undergraduate studies. B. Tech project another perfunctory exercise for most but critical for a very select few. You choose. They worked with Dr. Agarwal till the end of their time, May 2002. And they were staying at the campus for the summers, So Dr. Agarwal also decided to stay and they continued working on this problem.

Actually Nitin and Neeraj had both applied for Phds outside of IIT Kanpur. Nitin wanted to travel to the land of milk and honey and Neeraj to TIFR, but since Nitin did not get through anywhere he decided to continue with Dr. Agarwal. And since Nitin decided to continue, Neeraj also stayed on. They continued working on various aspects of the problem and they did find some interesting results but it never came to the point where it would hold true deterministically.

It was one morning in July 2002 that things suddenly came together – a bunch of facts they had discovered were floating around. Each of these observations were very simple in themselves but they suddenly came together to solve this problem. Dr. Agarwal called on his students to verify the results, which they did in a few days. They had finally found a solution to test if a number was a prime whose running time was a polynomial over the number of digits. He was very relieved to have solved this problem, a monkey he had been carrying on his back for about 4 years.

None of them had the slightest clue about how important a result this was and what consequence this would have. The News became public in Nov-Dec 2002. The awards have not stopped pouring ever since, including some of the most prestigious awards – The Clay Research Award, Delbert Ray Fulkerson Prize, G¨odel Prize along with other and other honorary awards like the Distinguished Alumnus Award at IIT Kanpur.

It is remarkable how few things happen and a lot others don’t. Now had he been able to cram words for GRE, or had his parents wanted him to go to the US or to the Civil Services, had he decided to pursue a more lucrative corporate career or had he not come across that paper in 1998. This story would not have been told.

The Clay Research Institute has seven unsolved problems, for which there is a combined prize of 7 million USD, a million a piece. The problem consist of Reimann Hypothesis, Poincare Conjecture*, Hodge Conjecture, Swinnerton-Dyer Conjecture, Solution of the Navier Stokes Theorem, Solution of Yang-Mills theory, and determination of whether NP-Problems are actually P-Problems.

Now who is smoking pot and roaming around the tennis court in his underpants?

I am Lost For Words as far as Dr. Agarwal’s story of Learning To Fly is concerned. We don’t need no Brain Drain, we need Brain Damage.

*Grigori Perelman solved the Poincare Conjecture, but refused to accept both the Fields Medal or the 1 million USD as the Millenium Prize, which was offered to him in 2010.

* Dr. Agarwal has been awarded a Padma Shri (4th Highest Civilian Award) by the Government of India on 26th Jan, 2013.



Leave a Comment
  1. Gauraw Singh Chandel / Jun 1 2012 11:55 am

    Very well written, Gyanesh!

  2. aritrak / Jun 1 2012 3:08 pm

    I must say thats was an inspiring story and very well constructed

  3. Rahul Raj / Jun 1 2012 7:07 pm

    can I post it on bhak sala Will text and leave the link

    • gyaneshpandey / Jun 2 2012 7:25 am

      Rahul – Use your own judgement to see if such a post might befit the forum. I have no issues. Best!

  4. umakant / Jun 1 2012 8:57 pm

    awesome dude, the story and story teller, both are upto the mark. keep it up, gp, I see a damn good writer in you, if you continue like this. What you are doing, I also feel is equally brave.

  5. Manish / Jun 1 2012 9:55 pm

    Awesome is the word. Some learning might be , “always explore yourself and secondly give 100% to whatever you do ” 🙂

  6. Apts / Jun 2 2012 1:38 am

    inspiring story – Ajay(Y00 batch)

  7. Madhuresh / Jun 2 2012 1:51 am

    Quite inspiring!!

  8. abhishek verma / Jun 2 2012 3:02 am

    First Clay Mathematics Institute Millennium Prize Announced for Resolution of the Poincaré Conjecture Awarded to Dr. Grigoriy Perelman .

    • gyaneshpandey / Jun 6 2012 5:17 pm

      Thanks for pointing this out. I’ll correct this.

  9. abhishek verma / Jun 2 2012 3:12 am

    nice content…the story of dr agarwal is an eye opener for those who paid huge fee for their Masters.

    • gyaneshpandey / Jun 2 2012 7:24 am

      Hehe. Is this the Abhishek Verma from 99 batch?

      • Ashwini Dixit / Jun 3 2012 5:24 pm

        I think of 2000 batch.. 🙂

      • abhishek verma / Jun 6 2012 8:25 pm

        no dude….

  10. Sumit / Jun 2 2012 5:28 am

    Great person with a great attitude! Salute to him!
    Coming to see you soon Dr.!

  11. Dig / Jun 2 2012 5:32 am

    “We don’t need no Brain Drain, we need Brain Damage.”
    Brilliantly put. Pink Floyd really seems to have influenced you.

    • gyaneshpandey / Jun 2 2012 7:22 am

      Yes I am very fond of them but the reason for using it so deliberately there was because of Dr. Agarwal’s liking for it.

  12. Shreya / Jun 2 2012 12:30 pm

    very nice article..wonderfully written! just want to say one far as i know, the poincare conjecture was solved somewhere in clay institute is left with 6 unsolved problems as of now. 🙂

    • gyaneshpandey / Jun 6 2012 5:19 pm

      Thanks. I’ll correct the Poincare Conjecture inconsistency.

  13. Himanshu Geed / Jun 2 2012 2:14 pm

    I’ve just read this piece and it’s nothing but sheer brilliance – not only on the part of Mr. Agarwal and his student, but by the writer who put this story together in such an awesome way.

    • gyaneshpandey / Jun 6 2012 5:20 pm

      Your generosity is totally appreciated. Thanks!

  14. Bijender Sheoran / Jun 2 2012 3:10 pm

    Very well researched and equally well articulated Gyanesh….I had heard bits and pieces of this during my stay at IITK, this provided a complete picture.
    Though for a second when you started describing the Halls and wing culture, I almost expected the mention of those much cherished midnight-ish Hall2-Hall3 traditions

  15. Pravin Kumar / Jun 2 2012 4:03 pm

    really inspiring and interesting………..hats off doctor agarwal

  16. J Phani Mahesh / Jun 2 2012 6:08 pm

    Reblogged this on PM and commented:
    Something I accidentally chanced upon.. And its worth a read, hence this reblog. 🙂 enjoy.

  17. Satyaanveshi / Jun 2 2012 6:09 pm

    Haha, interesting story 😀
    B.Tech from IITs is generally a waste of time 😀 But, as you pointed out, if one makes true friends and finds what he wants to do with the rest of his life at the end of 4/5 years, it’s worth the effort needed for getting in.

    • Anirudh / Jun 4 2012 12:41 am

      Whats makes you think Btech from IIT is a waste of time? IIT is worth every bright kid’s salt in India.

      • Satyaanveshi / Jun 4 2012 11:51 pm

        Wo!! I agree with you, sir, that getting there is tough.
        I and many of my friends feel that curriculum wise it was waste of time, just like the writer claims that Dr. Agarwal feels :). Perhaps it was our mistake. I am a 2010 passout, btw.

      • Koushik Viswanathan / Jun 5 2012 8:40 am

        Dont you think saying it is worth EVERY bright kid’s salt is taking it a little too far? Perhaps kids not interested in engineering are in some sense worthy of being called bright too?

        Everyone is entitled to a personal opinion and for good or for worse, here’s mine. Yes, IITs do provide several things that other colleges in the country simply cannot, but too much, in my view, has been made of an IIT education. Blame the media, blame the public. Blame whoever.

        As a result of this I think students who get into IIT often become too full of themselves and most of them cease to learn further.

  18. Satyaanveshi / Jun 2 2012 11:05 pm

    BTW, to be technically correct, there should be one less problem in your list. The Poincare Conjecture has been proved, that too by a very interesting bloke.

  19. Pratik Moona / Jun 2 2012 11:15 pm

    Just a side-note, Beatles and Zeppelin do have a huge following here in IITK… at least now! 🙂

  20. Dancing Fingers Singing Keypad / Jun 3 2012 6:12 am

    A friend emailed to share this blog link with the words: “I think this person is that simple unassuming (and smiling) guy with a backpack who asked a lot of questions about our project at Techkriti 2007”. Don’t know if this is who we think it is but enjoyed reading this post! 🙂 You write well, am following your blog.

    • gyaneshpandey / Jun 6 2012 5:25 pm

      Thanks for following this. Even though I would like to fit into the description you mention “simple unassuming (and smiling) guy with a backpack who asked a lot of questions”, I’m not that bloke. I graduated in 02 and have not attended Techkriti since.

      • Dancing Fingers Singing Keypad / Jun 13 2012 10:05 pm

        Actually, my friend clarified later that the guy he was referring to was Dr. Agarwal. Sorry for the misunderstanding but then it’s nice to have across your blog in the process 🙂

  21. Rohit / Jun 3 2012 8:46 am

    Very well written.

  22. Navin / Jun 3 2012 10:00 am

    Well written. I think most of us have some vague idea of Sir Manindra’s story. Thanks to the article which excited all of us by letting us see a big picture. Photo of the post seems to that of Abhineta Gyanesh ji(Senior)

  23. Vimal Kumar / Jun 3 2012 3:38 pm

    great work Gyanesh and thanks for bringing this to all of us…never knew this story!!!

  24. Koushik Viswanathan / Jun 3 2012 4:05 pm

    Very well written!

    On a side note, when you’re talking of brain drain and the need for it – I just looked it up, so please correct me if I’m wrong, isnt Nithin Saxena now a Professor in Germany? 🙂

  25. Ashwini Dixit / Jun 3 2012 5:25 pm

    capturing it is!!

  26. Gaurav / Jun 3 2012 9:59 pm

    Reblogged this on Life at IIT and commented:
    Must read for every IIT aspirant!!

  27. freakverse / Jun 4 2012 7:54 am

    Very nicely done. One thing – Prayag is just the ancient name for Allahabad, what you meant up there was ‘Sangam’?

  28. Aditya Bharti / Jun 4 2012 12:27 pm

    ill arrangement of paragraphs and made lengthier by repetitions & explanations though we imagined it before from ur previous sentences.
    overall it wazs
    Haha, interesting story

  29. Shivam Sharma / Jun 5 2012 4:05 pm

    Make a documentary over this article. That’d do some justice to it.

  30. Rupesh Mishra / Jun 5 2012 10:31 pm

    I always knew he is a great professor.I did not know the whole story of his life.
    Very well written .Awesome . 🙂

  31. Dr Gogna / Jul 18 2012 5:39 pm

    Well done Gyanesh. Keep writing more stories. We will look forward to it

  32. SK / Aug 7 2012 6:49 pm

    Brilliant narration. Needless to say, the brilliance of Professor and his students has been recognized by many…you narration needs more recognition.

  33. Ankur Agarwal / Aug 19 2012 1:11 pm

    Brilliant! Can you please share it on IITK facebook page for a wider audience ?

    • Gyanesh Pandey / Aug 22 2012 5:16 pm

      I did share it on IITK page, the same day i shared it myself. Feel free to share it yourself.

  34. Ansal / Aug 25 2012 4:27 am

    Just want to appreciate!

  35. Ratindra Sinha / Jan 4 2013 12:42 am

    I must say Gyanesh you’ve got nice talent to narrate the stories… a very well articulated piece of work.

  36. SHIJU P VARGHESE / Apr 10 2013 8:02 am

    a nice story written by by a brilliant writer

    • Gyanesh Pandey / Apr 10 2013 8:15 am

      Thanks! I’m not sure about the writer’s brilliance though.

  37. Deepak Sharma / Apr 17 2014 3:21 pm

    Hey are you close to Dr Agarwal or did you interview him ?

  38. Atul Kumar Srivastava / Jul 30 2015 5:31 am

    Very inspiring story for someone like me. From a small town he rose to great heights with his dedication to fulfill the dreams of his parents. I hope I could do even an inch of it for my parents.
    He inspires the young generation.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: