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.
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, 1992.  Berlin, 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, Cambridge, MA, 1985.  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.htmlMR 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 2m ± 1," Math. Comp., 29 (1975) 620--647.  MR 52:5546 [The article for the classical (n2 -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 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)
BP2001
R. Bhattacharjee and P. Pandey, "Primality testing," IIT Kanpur, (2001)
Bressoud89
D. M. Bressoud, Factorizations and primality testing, Springer-Verlag, 1989.  New York, NY, 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, 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].]
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, Amsterdam and New York, 1990.  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 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.]
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 · 109," Math. Comp., 35:151 (1980) 1003-1026.  MR 82g:10030 [See Richard Pinch's lists of pseudoprimes and [Jaeschke93].]
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, 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.]
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, 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