It is easy to determine whether a given integer is prime
Author:
Andrew Granville
Journal:
Bull. Amer. Math. Soc. 42 (2005), 338
MSC (2000):
Primary 11A51, 11Y11; Secondary 11A07, 11A41, 11B50, 11N25, 11T06
Published electronically:
September 30, 2004
MathSciNet review:
2115065
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
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
 1.
Leonard
M. Adleman and MingDeh
A. Huang, Primality testing and abelian varieties over finite
fields, Lecture Notes in Mathematics, vol. 1512, SpringerVerlag,
Berlin, 1992. MR
1176511 (93g:11128)
 2.
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 (84e:10008), http://dx.doi.org/10.2307/2006975
 3.
Manindra Agrawal, Neeraj Kayal and Nitin Saxena, PRIMES is in P (to appear).
 4.
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
(95k:11114), http://dx.doi.org/10.2307/2118576
 5.
R.
C. Baker and G.
Harman, The BrunTitchmarsh 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
(97h:11096)
 6.
D. J. Bernstein, 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).
 8.
Dan
Boneh, Twenty years of attacks on the RSA cryptosystem,
Notices Amer. Math. Soc. 46 (1999), no. 2,
203–213. MR
1673760
 9.
Richard
Crandall and Carl
Pomerance, Prime numbers, SpringerVerlag, New York, 2001. A
computational perspective. MR 1821158
(2002a:11007)
 10.
Whitfield
Diffie and Martin
E. Hellman, New directions in cryptography, IEEE Trans.
Information Theory IT22 (1976), no. 6,
644–654. MR 0437208
(55 #10141)
 11.
Étienne
Fouvry, Théorème de BrunTitchmarsh: application au
théorème de Fermat, Invent. Math. 79
(1985), no. 2, 383–407 (French). MR 778134
(86g:11052), http://dx.doi.org/10.1007/BF01388980
 12.
Morris
Goldfeld, On the number of primes 𝑝 for which
𝑝+𝑎 has a large prime factor, Mathematika
16 (1969), 23–27. MR 0244176
(39 #5493)
 13.
Andrew
Granville and Thomas
J. Tucker, It’s as easy as 𝑎𝑏𝑐,
Notices Amer. Math. Soc. 49 (2002), no. 10,
1224–1231. MR 1930670
(2003f:11044)
 14.
Shafi Goldwasser and Joe Kilian, 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.
 15.
Donald
E. Knuth, The art of computer programming. Vol. 2: Seminumerical
algorithms, AddisonWesley Publishing Co., Reading, Mass.LondonDon
Mills, Ont, 1969. MR 0286318
(44 #3531)
 16.
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
(87g:11171), http://dx.doi.org/10.1007/BFb0074800
 17.
H.W. Lenstra, Jr., and Carl Pomerance, Primality testing with Gaussian periods (to appear).
 18.
Yuri
V. Matiyasevich, Hilbert’s tenth problem, Foundations of
Computing Series, MIT Press, Cambridge, MA, 1993. Translated from the 1993
Russian original by the author; With a foreword by Martin Davis. MR 1244324
(94m:03002b)
 19.
Preda Mihailescu and Roberto Avanzi, Efficient `quasi  deterministic' primality test improving AKS (to appear).
 20.
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
(2001j:11086)
 21.
Paulo
Ribenboim, The new book of prime number records,
SpringerVerlag, New York, 1996. MR 1377060
(96k:11112)
 22.
José Felipe Voloch, On some subgroups of the multiplicative group of finite rings (to appear).
 1.
 Leonard M. Adleman and MingDeh A. Huang, Primality testing and abelian varieties over finite fields, Lecture Notes in Mathematics, vol. 1512, SpringerVerlag, Berlin. MR 1176511 (93g:11128)
 2.
 Leonard M. Adleman, Carl Pomerance and Robert S. Rumely, On distinguishing prime numbers from composite numbers, Annals of Mathematics 117 (1983), 173206. MR 0683806 (84e:10008)
 3.
 Manindra Agrawal, Neeraj Kayal and Nitin Saxena, PRIMES is in P (to appear).
 4.
 W. R. Alford, Andrew Granville and Carl Pomerance, There are infinitely many Carmichael numbers, Annals of Mathematics 139 (1994), 703722. MR 1283874 (95k:11114)
 5.
 Roger C. Baker and Glynn Harman, The BrunTitchmarsh Theorem on average, Progr. Math. 138 (1996), 39103. MR 1399332 (97h:11096)
 6.
 D. J. Bernstein, 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).
 8.
 Dan Boneh, Twenty years of attacks on the RSA Cryptosystem, Notices Amer. Math. Soc. 46 (1999), 203213. MR 1673760
 9.
 Richard Crandall and Carl Pomerance, Prime numbers. A computational perspective, SpringerVerlag, New York, 2001. MR 1821158 (2002a:11007)
 10.
 Whitfield Diffie and Martin E. Hellman, New directions in cryptography, IEEE Transactions on Information Theory 22 (1976), 644654. MR 0437208 (55:10141)
 11.
 Etienne Fouvry, Théorème de BrunTitchmarsh; application au théorème de Fermat, Invent. Math 79 (1985), 383407. MR 0778134 (86g:11052)
 12.
 Dorian M. Goldfeld, On the number of primes for which has a large prime factor, Mathematika 16 (1969), 2327. MR 0244176 (39:5493)
 13.
 Andrew Granville and Thomas Tucker, It's as easy as , Notices Amer. Math. Soc. 49 (2002), 12241231. MR 1930670 (2003f:11044)
 14.
 Shafi Goldwasser and Joe Kilian, 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.
 15.
 Donald E. Knuth, The art of computer programming, volume 2: Seminumerical algorithms, AddisonWesley, Reading, 1969. MR 0286318 (44:3531)
 16.
 H.W. Lenstra, Jr., Galois theory and primality testing, Lecture Notes in Mathematics 1142 (1985), 169189. MR 0812498 (87g:11171)
 17.
 H.W. Lenstra, Jr., and Carl Pomerance, Primality testing with Gaussian periods (to appear).
 18.
 Yu. V. Matijasevich, Hilbert's Tenth Problem, MIT Press, Cambridge, MA, 1993. MR 1244324 (94m:03002b)
 19.
 Preda Mihailescu and Roberto Avanzi, Efficient `quasi  deterministic' primality test improving AKS (to appear).
 20.
 Gérald Tenenbaum and Michel Mendès France, The Prime Numbers and Their Distribution, Student Mathematical Library 6 (2000), Amer. Math. Soc. MR 1756233 (2001j:11086)
 21.
 Paulo Ribenboim, The new book of prime number records, SpringerVerlag, New York, 1995. MR 1377060 (96k:11112)
 22.
 José Felipe Voloch, On some subgroups of the multiplicative group of finite rings (to appear).
Similar Articles
Retrieve articles in Bulletin of the American Mathematical Society
with MSC (2000):
11A51,
11Y11,
11A07,
11A41,
11B50,
11N25,
11T06
Retrieve articles in all journals
with MSC (2000):
11A51,
11Y11,
11A07,
11A41,
11B50,
11N25,
11T06
Additional Information
Andrew Granville
Affiliation:
Département de Mathématiques et Statistique, Université de Montréal, CP 6128 succ. CentreVille, Montréal, QC H3C 3J7, Canada
Email:
andrew@dms.umontreal.ca
DOI:
http://dx.doi.org/10.1090/S0273097904010377
PII:
S 02730979(04)010377
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.
Dedicated:
Dedicated to the memory of W. ‘Red’ Alford, friend and colleague
Article copyright:
© Copyright 2004 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
