## It is easy to determine whether a given integer is prime

HTML articles powered by AMS MathViewer

- by Andrew Granville PDF
- Bull. Amer. Math. Soc.
**42**(2005), 3-38 Request permission

## Abstract:

“The problem of distinguishing prime numbers from composite numbers, and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length. Nevertheless we must confess that all methods that have been proposed thus far are either restricted to very special cases or are so laborious and difficult that even for numbers that do not exceed the limits of tables constructed by estimable men, they try the patience of even the practiced calculator. And these methods do not apply at all to larger numbers ... It frequently happens that the trained calculator will be sufficiently rewarded by reducing large numbers to their factors so that it will compensate for the time spent. Further,*the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated*... It is in the nature of the problem that

*any*method will become more complicated as the numbers get larger. Nevertheless, in the following methods the difficulties increase rather slowly ... The techniques that were previously known would require intolerable labor even for the most indefatigable calculator.” —from article 329 of

*Disquisitiones Arithmeticae*(1801) by C. F. Gauss

## References

- Leonard M. Adleman and Ming-Deh A. Huang,
*Primality testing and abelian varieties over finite fields*, Lecture Notes in Mathematics, vol. 1512, Springer-Verlag, Berlin, 1992. MR**1176511**, DOI 10.1007/BFb0090185 - Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely,
*On distinguishing prime numbers from composite numbers*, Ann. of Math. (2)**117**(1983), no. 1, 173–206. MR**683806**, DOI 10.2307/2006975
3 Manindra Agrawal, Neeraj Kayal and Nitin Saxena, - W. R. Alford, Andrew Granville, and Carl Pomerance,
*There are infinitely many Carmichael numbers*, Ann. of Math. (2)**139**(1994), no. 3, 703–722. MR**1283874**, DOI 10.2307/2118576 - R. C. Baker and G. Harman,
*The Brun-Titchmarsh theorem on average*, Analytic number theory, Vol. 1 (Allerton Park, IL, 1995) Progr. Math., vol. 138, Birkhäuser Boston, Boston, MA, 1996, pp. 39–103. MR**1399332**
6 D. J. Bernstein, - Dan Boneh,
*Twenty years of attacks on the RSA cryptosystem*, Notices Amer. Math. Soc.**46**(1999), no. 2, 203–213. MR**1673760** - Richard Crandall and Carl Pomerance,
*Prime numbers*, Springer-Verlag, New York, 2001. A computational perspective. MR**1821158**, DOI 10.1007/978-1-4684-9316-0 - Whitfield Diffie and Martin E. Hellman,
*New directions in cryptography*, IEEE Trans. Inform. Theory**IT-22**(1976), no. 6, 644–654. MR**437208**, DOI 10.1109/tit.1976.1055638 - Étienne Fouvry,
*Théorème de Brun-Titchmarsh: application au théorème de Fermat*, Invent. Math.**79**(1985), no. 2, 383–407 (French). MR**778134**, DOI 10.1007/BF01388980 - Morris Goldfeld,
*On the number of primes $p$ for which $p+a$ has a large prime factor*, Mathematika**16**(1969), 23–27. MR**244176**, DOI 10.1112/S0025579300004575 - Andrew Granville and Thomas J. Tucker,
*It’s as easy as $abc$*, Notices Amer. Math. Soc.**49**(2002), no. 10, 1224–1231. MR**1930670**
14 Shafi Goldwasser and Joe Kilian, - Donald E. Knuth,
*The art of computer programming. Vol. 2: Seminumerical algorithms*, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR**0286318** - H. W. Lenstra Jr.,
*Galois theory and primality testing*, Orders and their applications (Oberwolfach, 1984) Lecture Notes in Math., vol. 1142, Springer, Berlin, 1985, pp. 169–189. MR**812498**, DOI 10.1007/BFb0074800
17 H.W. Lenstra, Jr., and Carl Pomerance, - Yu. V. Matiyasevich,
*Desyataya problema Gil′berta*, Matematicheskaya Logika i Osnovaniya Matematiki [Monographs in Mathematical Logic and Foundations of Mathematics], vol. 26, VO “Nauka”, Moscow, 1993 (Russian, with Russian summary). MR**1247235**
19 Preda Mihailescu and Roberto Avanzi, - Gérald Tenenbaum and Michel Mendès France,
*The prime numbers and their distribution*, Student Mathematical Library, vol. 6, American Mathematical Society, Providence, RI, 2000. Translated from the 1997 French original by Philip G. Spain. MR**1756233**, DOI 10.1090/stml/006 - Paulo Ribenboim,
*The new book of prime number records*, Springer-Verlag, New York, 1996. MR**1377060**, DOI 10.1007/978-1-4612-0759-7
22 José Felipe Voloch,

*PRIMES is in P*(to appear).

*Proving primality in essentially quartic random time*(to appear). 7 Pedro Berrizbeitia,

*Sharpening “PRIMES is in P” for a large family of numbers*(to appear).

*Almost all primes can be quickly certified*, Proceedings of the 18th annual ACM symposium on theory of computing, Association for Computing Machinery, New York, 1986.

*Primality testing with Gaussian periods*(to appear).

*Efficient ‘quasi - deterministic’ primality test improving AKS*(to appear).

*On some subgroups of the multiplicative group of finite rings*(to appear).

## Additional Information

**Andrew Granville**- Affiliation: Département de Mathématiques et Statistique, Université de Montréal, CP 6128 succ. Centre-Ville, Montréal, QC H3C 3J7, Canada
- MR Author ID: 76180
- ORCID: 0000-0001-8088-1247
- Email: andrew@dms.umontreal.ca
- Received by editor(s): January 27, 2004
- Received by editor(s) in revised form: August 19, 2004
- Published electronically: September 30, 2004
- Additional Notes: L’auteur est partiellement soutenu par une bourse du Conseil de recherches en sciences naturelles et en génie du Canada.
- © Copyright 2004
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Bull. Amer. Math. Soc.
**42**(2005), 3-38 - MSC (2000): Primary 11A51, 11Y11; Secondary 11A07, 11A41, 11B50, 11N25, 11T06
- DOI: https://doi.org/10.1090/S0273-0979-04-01037-7
- MathSciNet review: 2115065

Dedicated: Dedicated to the memory of W. ‘Red’ Alford, friend and colleague