Series: Penn State Logic Seminar

Date: Tuesday, December 3, 2002

Time: 2:30 - 3:45 PM

Place: 312 Boucke Building

Speaker: Carl Mummert, Mathematics, Penn State

Title: Primality Testing in Polynomial Time, part 2

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.