Abstract: Given a large positive integer , how quickly can one construct a prime number larger than (or between and )? Using probabilistic methods, one can obtain a prime number in time at most with high probability by selecting numbers between and 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 algorithm, and the best unconditional algorithm, due to Odlyzko, has a runtime of .
In this paper we discuss an approach that may improve upon the bound, by suggesting a strategy to determine in time for some whether a given interval in 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 in time .
Borodin and R.
Moenck, Fast modular transforms, J. Comput. System Sci.
8 (1974), 366–386. Thirteenth Annual IEEE Symposium
on Switching and Automata Theory (Univ. Maryland, College Park, Md., 1972).
0371144 (51 #7365)
H. Cramér, On the order of magnitude of the difference between consecutive prime numbers, Acta Arithmetica 2 (1936), 23-46.
Tenenbaum, Introduction to analytic and probabilistic number
theory, Cambridge Studies in Advanced Mathematics, vol. 46,
Cambridge University Press, Cambridge, 1995. Translated from the second
French edition (1995) by C. B. Thomas. MR 1342300
G. Tenenbaum, Introduction to analytic and probabilistic number theory. Translated from the second French edition (1995) by C. B. Thomas. Cambridge Studies in Advanced Mathematics, 46. Cambridge University Press, Cambridge, 1995. MR 1342300 (97e:11005b)