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

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.**Manindra Agrawal, Neeraj Kayal, and Nitin Saxena,*PRIMES is in P*, Ann. of Math. (2)**160**(2004), no. 2, 781–793. MR**2123939**, https://doi.org/10.4007/annals.2004.160.781**2.**R. C. Baker, G. Harman, and J. Pintz,*The difference between consecutive primes. II*, Proc. London Math. Soc. (3)**83**(2001), no. 3, 532–562. MR**1851081**, https://doi.org/10.1112/plms/83.3.532**3.**A. 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). MR**0371144**, https://doi.org/10.1016/S0022-0000(74)80029-2**4.**H. Cramér,*On the order of magnitude of the difference between consecutive prime numbers*, Acta Arithmetica 2 (1936), 23-46.**5.**M. Deléglise and J. Rivat,*Computing 𝜋(𝑥): the Meissel, Lehmer, Lagarias, Miller, Odlyzko method*, Math. Comp.**65**(1996), no. 213, 235–245. MR**1322888**, https://doi.org/10.1090/S0025-5718-96-00674-6**6.**Andrew Granville,*Harald Cramér and the distribution of prime numbers*, Scand. Actuar. J.**1**(1995), 12–28. Harald Cramér Symposium (Stockholm, 1993). MR**1349149**, https://doi.org/10.1080/03461238.1995.10413946**7.**D. R. Heath-Brown,*Primes represented by 𝑥³+2𝑦³*, Acta Math.**186**(2001), no. 1, 1–84. MR**1828372**, https://doi.org/10.1007/BF02392715**8.**J. C. Lagarias, V. S. Miller, and A. M. Odlyzko,*Computing 𝜋(𝑥): the Meissel-Lehmer method*, Math. Comp.**44**(1985), no. 170, 537–560. MR**777285**, https://doi.org/10.1090/S0025-5718-1985-0777285-5**9.**J. C. Lagarias and A. M. Odlyzko,*Computing 𝜋(𝑥): an analytic method*, J. Algorithms**8**(1987), no. 2, 173–191. MR**890871**, https://doi.org/10.1016/0196-6774(87)90037-X**10.**D.H.J. Polymath,`michaelnielsen.org/polymath1/index.php?title=Polymath1`**11.**Volker Strassen,*Gaussian elimination is not optimal*, Numer. Math.**13**(1969), 354–356. MR**0248973**, https://doi.org/10.1007/BF02165411**12.**Gérald 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****13.**I. M. Vinogradov,*Elements of number theory*, Dover Publications, Inc., New York, 1954. Translated by S. Kravetz. MR**0062138**

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