← All research spotlights

Research spotlight · Unit 3

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.

The paper

Agrawal, M., Kayal, N., and Saxena, N. (2004). PRIMES is in P. Annals of Mathematics, 160(2), 781‑793. https://doi.org/10.4007/annals.2004.160.781

The scientists named here are not contributors to the NT Masterclass, are not affiliated with it, and have not endorsed it. The program presents and explains their published research, with references to the original papers.