Deterministic methods to find primes

Abstract

Given a large positive integer $N$, how quickly can one construct a prime number larger than $N$ (or between $N$ and 2N)? Using probabilistic methods, one can obtain a prime number in time at most ${\log }^{O(1)}N$ with high probability by selecting numbers between $N$ and 2N at random and testing each one in turn for primality until a prime is discovered. However, if one seeks a deterministic method, then the problem is much more difficult, unless one assumes some unproven conjectures in number theory; brute force methods give a $O(N^{1+o(1)})$ algorithm, and the best unconditional algorithm, due to Odlyzko, has a run time of $O(N^{1/2+o(1)})$. In this paper we discuss an approach that may improve upon the $O(N^{1/2+o(1)})$ bound, by suggesting a strategy to determine in time $O(N^{1/2-c})$ for some $c>0$ whether a given interval in $[N,2N]$ contains a prime. While this strategy has not been fully implemented, it can be used to establish partial results, such as being able to determine the \emph{parity} of the number of primes in a given interval in $[N,2N]$ in time $O(N^{1/2-c})$.

15 pages, no figures. A reference added. (Note also that the published version lists the main contributors to the project as authors, at the insistence of the journal.)