Basic Notions Seminar talk on November 21, 2002

Speaker:   Joe Buhler (Reed College)

Title:   Primality is "Easy"

Abstract: 
    Late this summer, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena (two of whom are undergraduates) released a preprint that contained a bombshell: they showed that there is a deterministic polynomial-time algorithm that determines whether an integer is a prime. Although this result has long been conjectured, such an algorithm has eluded people for many years.
    This talk will explain their algorithm, the ideas behinds the proof of its correctness, and recent improvements due to Lenstra and Pomerance.