Colloquium Details
Primality is "Easy"
| Author: | Joe Buhler Reed College |
|---|---|
| Date: | November 21, 2002 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
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.