GRH and polynomial-time primality testing

GRH and polynomial-time primality testing

-
Jacob Tsimerman, Princeton University
Fine Hall 314

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.