  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})$.
