A new primal screen
Speaker: Carl Pomerance, Dartmouth College
Date and time: Thursday, March 10, 2005, 4:00–4:55 p.m.
Location: Little Hall, Room 113
Opening remarks: Win Phillips, Vice-President for Research
Refreshments: After the lecture, Little Hall, Room 339 (the Atrium)
Abstract
How fast can one determine if a given number is prime or composite? This question, which was first posed explicitly by Gauss in 1801, has been the subject of much attention in the computer age. In 2002, Agrawal, Kayal and Saxena announced a new and surprisingly simple deterministic algorithm that runs in polynomial time (within a fixed power of the number of digits of the number in question). We will discuss this algorithm as well as more recent developments.
About the speaker
Carl Pomerance is a world famous number theorist and one of the pre-eminent authorities in the areas of primality testing and factoring of large integers which have applications to cryptography. One of his fundamental contributions is the quadratic sieve algorithm. After receiving his PhD from Harvard University, he joined the University of Georgia as an assistant professor and rose to the rank of Distinguished Professor there. Then he worked at Lucent Technologies for a few years and is currently a Distinguished Professor at Dartmouth.