GRH and polynomial-time primality testing

Thursday, October 9, 2008 -
12:30pm to 2:30pm
For a long time, a famous open problem was to figure out whether a number was prime quickly (in polynomial time). It's interesting to see how under the generalized riemann hypothesis, the problem becomes completely straightforward. I will introduce the relevant concept and present the simple proof. During the second half, I will present a provably polynomial time test, without reliance on GRH. If time permits, I will say some more about L-functions and their application to computing.
Speaker: 
Jacob Tsimerman
Princeton University
Event Location: 
Fine Hall 314