Manindra Agrawal
Indian Institute of Technology Kanpur
- Research field
- Computational complexity, primality testing, algebraic algorithms
Manindra Agrawal works on the complexity of computation, the question of which problems a computer can solve efficiently. In 2002, with his students Neeraj Kayal and Nitin Saxena, he gave the first algorithm that decides whether a number is prime in polynomial time without random choices and without unproved assumptions, a question that had been open for decades. The test rests on a polynomial version of Fermat's little theorem and a counting argument. The unit presents it as the answer to the question of why primality can be decided quickly while factoring cannot.
In the masterclass
Section 6, after the comparison of recognizing primes with factoring, presents the polynomial-time primality test of Agrawal, Kayal, and Saxena.
The research is presented in Unit 3: Prime Numbers and Unique Factorization, in a research spotlight box that explains the result at the level of the unit and links it to what you have just learned.