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 logO(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 prob-lem is much more difficult, unless one assumes some unproven conjectures in number theory; brute force methods give a O(N1+o(1)) algorithm, and the best unconditional algorithm, due to Odlyzko, has a runtime of O(N1/2+o(1)). In this paper we discuss an approach that may improve upon the O(N1/2+o(1)) bound, by suggesting a strategy to determine in time O(N1/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 parity of the number of primes in a given interval in [N, 2N] in time O(N1/2−c). 1