May 23, 2003 -- 3:30 pm
A Polynomial-time Algorithm for Primality Testing
Manindra Agrawal was born in May 1966, and since 2001 he has been a
full professor at the Indian Institute of Technology in Kanpur, India.
He has been active over the past ten years in the field of decision
theory, complexity, and the relation between the geometry of sets and
their information content. For some years he has been interested in
finding a polynomial time algorithm to test whether a given number is
prime. Although random algorithms can solve this problem with high certainty
in polynomial time, it remained a long-standing challenge to find a
method that works in every case.
To the great surprise of the experts, Agrawal solved this problem in
August 2002, working together with two undergraduate students: Neeraj
Kayal and Nitin Saxena. Their proof establishes the correctness of a
conjecture made in 1999 by Agrawal and Biswas.