Finding primes & proving primality
References for primality proving pages
Primality Proving Icon
Home > Primality Proving > References
These are the references used in our primality proving pages. They are a subset of the Prime Pages' references.
M. Agrawal and S. Biswas, Primality and identity testing via Chinese remaindering.  In "40th Annual Symposium on Foundations of Computer Science (New York, 1999)," IEEE Computer Soc., Los Alamitos, CA, 1999.  pp. 202--208, MR1917560
W. R. Alford, A. Granville and C. Pomerance, "There are infinitely many Carmichael numbers," Ann. of Math. (2), 139 (1994) 703--722.  MR 95k:11114
L. M. Adlemann and M. D. Huang, Primality testing and two dimensional Abelian varieties over finite fields., Lecture Notes in Mathematics Vol, 1512, Springer-Verlag, 1992.  Berlin, pp. viii+142, ISBN 3-540-55308-8. MR 93g:11128
M. Agrawal, N. Kayal and N. Saxena, "PRIMES in P," Ann. of Math. (2), 160:2 (2004) 781--793.  Available from
Abstract: We present a deterministic polynomial-time algorithm that determines whether an input number n is prime or composite.
A. O. L. Atkin and F. Morain, "Elliptic curves and primality proving," Math. Comp., 61:203 (July 1993) 29--68.  MR 93m:11136
L. M. Adleman, C. Pomerance and R. S. Rumely, "On distinguishing prime numbers from composite numbers," Ann. Math., 117:1 (1983) 173--206.  MR 84e:10008 [The first of the modern primality tests.]
A. O. L. Atkin, "Lecture notes of a conference," Boulder Colorado, (August 1986) Manuscript. [See also [AM93].]
E. Bach, Analytic methods in the analysis and design of number-theoretic algorithms, A.C.M. Distinguished Dissertations The MIT Press, Cambridge, MA, 1985.  pp. xiii+48, ISBN 0-262-02219-2. MR 87i:11185
D. Berstein, "Detecting perfect powers in essentially linear time," Math. Comp., 67:223 (1998) 1253--1283.  Available from 98j:11121 (Abstract available)
D. J. Bernstein, "Proving primality in essentially quartic random time," (2003) Draft available from
Abstract: This paper presents an algorithm that, given a prime n, finds and verifies a proof of the primality of n in random time (lg n)4+o(1).
P. Berrizbeitia, "Sharpening "Primes is in P" for a large family of numbers," (2003) Available from (Annotation available)
E. Bach and L. Huelsbergen, "Statistical evidence for small generating sets," Math. Comp., 61:203 (1993) 69--82.  MR1195432
R. C. Baker and G. Harman, The Brun-Titchmarsh theorem on average.  In "Proc. Conf. in Honor of Heini Halberstam (Allerton Park, IL, 1995)," Progr. Math. Vol, 138, Birkhäuser Boston, Boston, MA, 1996.  pp. 39--103, MR 97h:11096
W. Bosma and M. P. van der Hulst, Faster primality testing.  In "Advances in Cryptology--EUROCRYPT '89 Proceedings," J. J. Quisquater and J. Vandewalle editors, Springer-Verlag, 1990.  pp. 652--656,
J. Brillhart, D. H. Lehmer and J. L. Selfridge, "New primality criteria and factorizations of 2m ± 1," Math. Comp., 29 (1975) 620--647.  MR 52:5546 [The article for the classical (n2 -1) primality tests. Table errata in [Brillhart1982]]
J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman and S. S. Wagstaff, Jr., Factorizations of bn ± 1, b=2,3,5,6,7,10,12 up to high powers, Amer. Math. Soc., 1988.  Providence RI, pp. xcvi+236, ISBN 0-8218-5078-4. MR 90d:11009 (Annotation available)
R. Bhattacharjee and P. Pandey, "Primality testing," IIT Kanpur, (2001)
D. M. Bressoud, Factorizations and primality testing, Springer-Verlag, 1989.  New York, NY, ISBN 0387970401. MR 91e:11150 [QA161.F3B73]
Q. Cheng, "Primality proving via one round of ECPP and one iteration in AKS," Crypto 2003, Santa Barbara, (2003) Available from
H. Cohen and Lenstra, Jr., H. W., "Primality testing and Jacobi sums," Math. Comp., 42 (1984) 297--330.  MR 86g:11078 [APRT-CL test introduced.]
H. Cohen and A. K. Lenstra, "Implementation of a new primality test," Math. Comp., 48 (1987) 103--121.  MR 88c:11080 [APRT-CL test implemented.]
R. Crandall and C. Pomerance, Prime numbers: a computational perspective, Springer-Verlag, New York, NY, 2001.  pp. xvi+545, ISBN 0-387-94777-9. MR 2002a:11007 (Abstract available) [This is a valuable text written by true experts in two different areas: computational and theoretical respectively. There is now a second edition [CP2005].]
E. Fouvry, "Théorème de Brun-Titchmarsh; application au théorèm de Fermat," Ivent. Math., 79:2 (1985) 383--407.  MR 86g:11052
S. Goldwasser and J. Kilian, Almost all primes can be quickly certified.  In "STOC'86, Proceedings of the 18th Annual ACM Symposium on the Theory of Computing (Berkeley, CA, 1986)," ACM, New York, NY, May 1986.  pp. 316--329,
J. Grantham, "Frobenius pseudoprimes," Math. Comp., 70 (2001) 873--891.  MR 2001g:11191 (Abstract available)
J. Grantham, "A probable prime test with high confidence," J. Number Theory, 72 (1998) 32--47.  MR 2000e:11160
G. H. Hardy and J. E. Littlewood, "Some problems of `partitio numerorum' : III: on the expression of a number as a sum of primes," Acta Math., 44 (1923) 1-70.  Reprinted in "Collected Papers of G. H. Hardy," Vol. I, pp. 561-630, Clarendon Press, Oxford, 1966.
G. Jaeschke, "On strong pseudoprimes to several bases," Math. Comp., 61 (1993) 915-926.  MR 94d:11004
N. Kayal and N. Saxena, "Towards adeterministic polynomial-time test," (2002) Available from
D. N. Lehmer, "An extended theory of Lucas' functions," Ann. Math., 31 (1930) 419-448.  Reprinted in Selected Papers, D. McCarthy editor, v. 1, Ch. Babbage Res. Center, St. Pierre, Manitoba Canada, pp. 11-48 (1981).
Lenstra, Jr., A. K. and Lenstra, Jr., H. W., Algorithms in number theory.  In "Handbook of Theoretical Computer Science, Vol A: Algorithms and Complexity," The MIT Press, Amsterdam and New York, 1990.  pp. 673-715, MR 1 127 178
P. Mihailescu, Cyclotomy primality proving -- recent developments.  In "Proceedings of the III Applied Number Theory Seminar, ANTS III, Portland, Oregon 1998," Lecture Notes in Computer Science Vol, 1423, 1998.  pp. 95--110, MR 2000j:11195
G. Miller, "Riemann's hypothesis and tests for primality," J. Comput. System Sci., 13 (1976) 300--317.  MR 58:470a
L. Monier, "Evaluation and comparsion of two efficient probablistic primality testing algorithms," Theoretical Computer Science, 12:1 (1980) 97--108.  MR 82a:68078
M. Morrison, "A note on primality testing using Lucas sequences," Math. Comp., 29 (1975) 181--182.  MR 51:5469
Oesterlé, J., Versions effectives du théorème de chebotarev sous l'hypothèse de riemann généralisée.  In "Journ{\'e}es Arithm{\'e}tiques de Luminy (20 Juin--24 Juin 1978)," Astérisque 61 Société Mathématique de France, Paris, 1979.  pp. 165--167,
R. Pinch, "The Carmichael numbers up to 1015," Math. Comp., 61:203 (1993) 381-391.  MR 93m:11137 [A preprint and several data files may be found in the Carmichael directory of his FTP site. For example, he lists the Carmichaels to 1017.]
C. Pomerance, Lecture notes on primality testing and factoring (notes by G. M. Gagola Jr.), Notes Vol, 4, Mathematical Association of America, 1984.  pp. 34 pages,
C. Pomerance, J. L. Selfridge and Wagstaff, Jr., S. S., "The pseudoprimes to 25 · 109," Math. Comp., 35:151 (1980) 1003-1026.  MR 82g:10030 [See Richard Pinch's lists of pseudoprimes and [Jaeschke93].]
M. O. Rabin, "Probabilistic algorithm for testing primality," J. Number Theory, 12 (1980) 128--138.  MR 81f:10003
P. Ribenboim, The new book of prime number records, 3rd edition, Springer-Verlag, 1995.  New York, NY, pp. xxiv+541, ISBN 0-387-94457-5. MR 96k:11112 [An excellent resource for those with some college mathematics. Basically a Guinness Book of World Records for primes with much of the relevant mathematics. The extensive bibliography is seventy-five pages.]
H. Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics Vol, 126, Birkhäuser Boston, Boston, MA, 1994.  ISBN 0-8176-3743-5. MR 95h:11142 [An excellent reference for those who want to start to program some of these algorithms. Code is provided in Pascal. Previous edition was vol. 57, 1985.]
A. Wiles, "Modular elliptic curves and Fermat's last theorem," Ann. Math., 141:3 (1995) 443--551.  MR 96d:11071 (Annotation available)
H. C. Williams, "Primality testing on a computer," Ars Combin., 5 (1978) 127--185.  MR 80d:10002 [A survey of the classical primality tests.]
H. C. Williams, Édouard Lucas and primality testing, Canadian Math. Soc. Series of Monographs and Adv. Texts Vol, 22, John Wiley \& Sons, 1998.  New York, NY, pp. x+525, ISBN 0-471-14852-0. MR 2000b:11139 (Annotation available)
[ table of contents | previous page ]
The Prime Pages © Chris Caldwell