10/28/2002

Manindra Agrawal
Kanpur, India

Determining if a given number is prime has engaged the attention of theoretical computer scientists for several decades. Several efforts have been made to design an efficient (in other words, polynomial-time) algorithm.These include Miller’s test (a polynomial-time algorithm; however, it is correct only assuming Extended Riemann Hypothesis), Rabin’s and Solovey-Strassen’s tests (randomized polynomial-time tests), Adelman-Pomerance-Rumeli’s test (deterministic test requiring slightly super-polynomial time), etc.It has remained a major open problem to design an unconditional deterministic polynomial-time algorithm for the problem. In this talk, we present the first such algorithm.