Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
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 $ 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 runtime 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 parity of the number of primes in a given interval in $ [N,2N]$ in time $ O(N^{1/2-c})$.

References [Enhancements On Off] (What's this?)

  • 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 $ \pi(x)$: 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 $ x^3+2y^3$. Acta Math. 186 (2001), no. 1, 1-84. MR 1828372 (2002b:11122)
  • 8. J. C. Lagarias, V. S. Miller, A. M. Odlyzko, Computing $ \pi(x)$: The Meissel-Lehmer method, Math. Comp. 44 (1985), 537-560. MR 777285 (86h:11111)
  • 9. J. C. Lagarias, A. M. Odlyzko, Computing $ \pi(x)$: An analytic method, J. Algorithms 8 (1987), 173-191. MR 890871 (88k:11095)
  • 10. D.H.J. Polymath,
  • 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)

Similar Articles

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

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

Additional Information

Terence Tao

Ernest Croot III

Harald Helfgott

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

American Mathematical Society