Deterministic methods to find primes

Authors:
Terence Tao, Ernest Croot III and Harald Helfgott

Journal:
Math. Comp. **81** (2012), 1233-1246

MSC (2010):
Primary 11Y11

DOI:
https://doi.org/10.1090/S0025-5718-2011-02542-1

Published electronically:
August 23, 2011

MathSciNet review:
2869058

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 .

**1.**M. Agrawal, N. Kayal, N. Saxena,*PRIMES is in P*, Annals of Mathematics**160**(2004), no. 2, pp. 781-793. MR**2123939 (2006a:11170)****2.**R. C. Baker, G. Harman, J. Pintz,*The difference between consecutive primes*, II, Proceedings of the London Mathematical Society**83**, (2001), 532-562. MR**1851081 (2002f:11125)****3.**A. Borodin, R. Moenk,*Fast Modular Transforms*, Jour. of Comp. and System Sciences,**8**(1974), 366-386. MR**0371144 (51:7365)****4.**H. Cramér,*On the order of magnitude of the difference between consecutive prime numbers*, Acta Arithmetica 2 (1936), 23-46.**5.**M. Deleglise, J. Rivat,*Computing : the Meissel, Lehmer, Lagarias, Miller, Odlyzko method*, Math. Comp. Vol. 65 (1996), 235-245. MR**1322888 (96d:11139)****6.**A. Granville,*Harald Cramér and the distribution of prime numbers*, Scandinavian Actuarial Journal 1(1995), 12-28. MR**1349149 (96g:01002)****7.**D. R. Heath-Brown,*Primes represented by*. Acta Math. 186 (2001), no. 1, 1-84. MR**1828372 (2002b:11122)****8.**J. C. Lagarias, V. S. Miller, A. M. Odlyzko,*Computing : The Meissel-Lehmer method*, Math. Comp. 44 (1985), 537-560. MR**777285 (86h:11111)****9.**J. C. Lagarias, A. M. Odlyzko,*Computing : An analytic method*, J. Algorithms 8 (1987), 173-191. MR**890871 (88k:11095)****10.**D.H.J. Polymath,`michaelnielsen.org/polymath1/index.php?title=Polymath1`**11.**V. Strassen,*Gaussian elimination is not optimal*, Numer. Math. 13 (1969), 354-356. MR**0248973 (40:2223)****12.**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)****13.**I. M. Vinogradov, Elements of Number Theory, Mineola, NY: Dover Publications, 2003, MR**0062138 (15:933e)**

Retrieve articles in *Mathematics of Computation*
with MSC (2010):
11Y11

Retrieve articles in all journals with MSC (2010): 11Y11

Additional Information

**Terence Tao**

Affiliation:
http://michaelnielsen.org/polymath1/index.php

**Ernest Croot III**

Affiliation:
http://michaelnielsen.org/polymath1/index.php

**Harald Helfgott**

Affiliation:
http://michaelnielsen.org/polymath1/index.php

DOI:
https://doi.org/10.1090/S0025-5718-2011-02542-1

Received by editor(s):
September 20, 2010

Received by editor(s) in revised form:
February 17, 2011, and February 23, 2011

Published electronically:
August 23, 2011

Article copyright:
© Copyright 2011
American Mathematical Society