Series: Penn State Logic Seminar Date: Tuesday, November 26, 2002 Time: 2:30 - 3:45 PM Place: 312 Boucke Building Speaker: Carl Mummert, Mathematics, Penn State Title: Primality Testing in Polynomial Time, part 1 Abstract: The problem "Is PRIMES in P?" was solved in August 2002 by Agrawal, Kayal, and Saxena. They produced an algorithm which, in polynomial time, can determine if an integer is prime or composite. In this talk, I will prove that their algorithm runs in polynomial time. I will briefly discuss how the bound on the running time can be improved if a certain conjecture about the distribution of prime numbers is assumed. No previous knowledge of number theory or computational complexity is assumed.
Mathematical Logic at Penn State
Department of Mathematics