We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Department of Mathematical Sciences

Seminar Archives

On this page you can find information about seminars in this and previous academic years, where available on the database.

Pure Maths Colloquium: Finding primes deterministically

Presented by Harald Helfgott, Bristol University

7 March 2011 17:15 in CM221

Take a large number N. How do you find a prime between N and 2N? Since primes are fairly dense, and since we can test whether an integer is a prime rapidly, constructing a probabilistic algorithm for finding a prime rapidly is trivial. What about a deterministic algorithm? If we could check quickly whether there is a prime in an interval [N,N+M], M<=N, we would be done. This goal still seems distant. However, we do have now a non-trivial result that is weaker in two ways: the algorithm checks the parity of the number of primes in [N,N+M], rather than whether there are any; moreover, the running time, N^{0.5-c}, is much larger than the desired (log N)^C, though it does break the N^{0.5} barrier. [The results in the talk were part of a Polymath project. Other main participants include Ernie Croot and Terence Tao.]

Contact for more information