Finding primes & proving primality References for primality proving pages Home > Primality Proving > References

AB1999

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

AGP94

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

AH1992

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, Berlin, 1992.  pp. viii+142, ISBN 3-540-55308-8. MR 93g:11128

AKS2002

M. Agrawal, N. Kayal and N. Saxena, "PRIMES in P," Ann. of Math. (2), 160:2 (2004) 781--793.  Available from http://www.cse.iitk.ac.in/users/manindra/.  MR2123939

Abstract: We present a deterministic polynomial-time algorithm that determines whether an input number n is prime or composite.

AM93

A. O. L. Atkin and F. Morain, "Elliptic curves and primality proving," Math. Comp., 61:203 (July 1993) 29--68.  MR 93m:11136

APR83

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.]

Atkin86

A. O. L. Atkin, "Lecture notes of a conference," Boulder Colorado, (August 1986) Manuscript. [See also [AM93].]

Bach85

E. Bach, Analytic methods in the analysis and design of number-theoretic algorithms, A.C.M. Distinguished Dissertations The MIT Press, 1985.  Cambridge, MA, pp. xiii+48, ISBN 0-262-02219-2. MR 87i:11185

Bernstein1998b

D. Berstein, "Detecting perfect powers in essentially linear time," Math. Comp., 67:223 (1998) 1253--1283.  Available from http://cr.yp.to/papers.html.  MR 98j:11121 (Abstract available)

Bernstein2003

D. J. Bernstein, "Proving primality in essentially quartic random time," (2003) Draft available from http://cr.yp.to/papers.html.

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).

Berrizbeitia2003

P. Berrizbeitia, "Sharpening "Primes is in P" for a large family of numbers," (2003) Available from http://arxiv.org/abs/math.NT/0211334. (Annotation available)

BH1993

E. Bach and L. Huelsbergen, "Statistical evidence for small generating sets," Math. Comp., 61:203 (1993) 69--82.  MR1195432

BH1996

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

BH90

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,

BLS75

J. Brillhart, D. H. Lehmer and J. L. Selfridge, "New primality criteria and factorizations of 2^m ± 1," Math. Comp., 29 (1975) 620--647.  MR 52:5546 [The article for the classical (n² -1) primality tests. Table errata in [Brillhart1982]]

BLSTW88

J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman and S. S. Wagstaff, Jr., Factorizations of bⁿ ± 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)

BP2001

R. Bhattacharjee and P. Pandey, "Primality testing," IIT Kanpur, (2001)

Bressoud89

D. M. Bressoud, Factorizations and primality testing, Springer-Verlag, New York, NY, 1989.  ISBN 0387970401. MR 91e:11150 [QA161.F3B73]

Cheng2003

Q. Cheng, "Primality proving via one round of ECPP and one iteration in AKS," Crypto 2003, Santa Barbara, (2003) Available from http://www.cs.ou.edu/~qcheng/.

CL84

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.]

CL87

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.]

CP2001

R. Crandall and C. Pomerance, Prime numbers: a computational perspective, Springer-Verlag, 2001.  New York, NY, 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].]

F1985

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

GK86

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,

Grantham2000

J. Grantham, "Frobenius pseudoprimes," Math. Comp., 70 (2001) 873--891.  MR 2001g:11191 (Abstract available)

Grantham98

J. Grantham, "A probable prime test with high confidence," J. Number Theory, 72 (1998) 32--47.  MR 2000e:11160

HL23

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.

Jaeschke93

G. Jaeschke, "On strong pseudoprimes to several bases," Math. Comp., 61 (1993) 915-926.  MR 94d:11004

KS2002

N. Kayal and N. Saxena, "Towards adeterministic polynomial-time test," (2002) Available from http://www.cse.iitk.ac.in/research/btp2002/primality.html.

Lehmer30

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).

LL90

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, 1990.  Amsterdam and New York, pp. 673-715, MR 1 127 178

Mihailescu98

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

Miller76

G. Miller, "Riemann's hypothesis and tests for primality," J. Comput. System Sci., 13 (1976) 300--317.  MR 58:470a

Monier80

L. Monier, "Evaluation and comparsion of two efficient probablistic primality testing algorithms," Theoretical Computer Science, 12:1 (1980) 97--108.  MR 82a:68078

Morrison75

M. Morrison, "A note on primality testing using Lucas sequences," Math. Comp., 29 (1975) 181--182.  MR 51:5469

Osterle1979

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,

Pinch93

R. Pinch, "The Carmichael numbers up to 10¹⁵," Math. Comp., 61:203 (1993) 381-391.  MR 93m:11137

Pomerance84

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,

PSW80

C. Pomerance, J. L. Selfridge and Wagstaff, Jr., S. S., "The pseudoprimes to 25 · 10⁹," Math. Comp., 35:151 (1980) 1003-1026.  MR 82g:10030

Rabin80

M. O. Rabin, "Probabilistic algorithm for testing primality," J. Number Theory, 12 (1980) 128--138.  MR 81f:10003

Ribenboim95

P. Ribenboim, The new book of prime number records, 3rd edition, Springer-Verlag, New York, NY, 1995.  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.]

Riesel94

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.]

Wiles95

A. Wiles, "Modular elliptic curves and Fermat's last theorem," Ann. Math., 141:3 (1995) 443--551.  MR 96d:11071 (Annotation available)

Williams78

H. C. Williams, "Primality testing on a computer," Ars Combin., 5 (1978) 127--185.  MR 80d:10002 [A survey of the classical primality tests.]

Williams98

H. C. Williams, Édouard Lucas and primality testing, Canadian Math. Soc. Series of Monographs and Adv. Texts Vol, 22, John Wiley \& Sons, New York, NY, 1998.  pp. x+525, ISBN 0-471-14852-0. MR 2000b:11139 (Annotation available)