Primality testing and Jacobi sums

Cohen, H.; Lenstra, H. W.

doi:10.1090/S0025-5718-1984-0726006-X

Primality testing and Jacobi sums
HTML articles powered by AMS MathViewer

by H. Cohen and H. W. Lenstra PDF

Math. Comp. 42 (1984), 297-330 Request permission

Abstract:

We present a theoretically and algorithmically simplified version of a primality testing algorithm that was recently invented by Adleman and Rumely. The new algorithm performs well in practice. It is the first primality test in existence that can routinely handle numbers of hundreds of decimal digits.

References

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
John Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria and factorizations of $2^{m}\pm 1$, Math. Comp. 29 (1975), 620–647. MR 384673, DOI 10.1090/S0025-5718-1975-0384673-1
D. A. Burgess, On the quadratic character of a polynomial, J. London Math. Soc. 42 (1967), 73–80. MR 205940, DOI 10.1112/jlms/s1-42.1.73
G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
Helmut Hasse, Zahlentheorie, Akademie-Verlag, Berlin, 1963 (German). Zweite erweiterte Auflage. MR 0153659
Helmut Hasse, Zahlentheorie, Akademie-Verlag, Berlin, 1969 (German). Dritte berichtigte Auflage. MR 0253972
Jean-René Joly, Équations et variétés algébriques sur un corps fini, Enseign. Math. (2) 19 (1973), 1–117 (French). MR 327723
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
J. C. Lagarias, H. L. Montgomery, and A. M. Odlyzko, A bound for the least prime ideal in the Chebotarev density theorem, Invent. Math. 54 (1979), no. 3, 271–296. MR 553223, DOI 10.1007/BF01390234
Serge Lang, Algebra, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1965. MR 0197234
Serge Lang, Algebraic number theory, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970. MR 0282947
Serge Lang, Cyclotomic fields, Graduate Texts in Mathematics, Vol. 59, Springer-Verlag, New York-Heidelberg, 1978. MR 0485768
D. H. Lehmer, On Fermat’s quotient, base two, Math. Comp. 36 (1981), no. 153, 289–290. MR 595064, DOI 10.1090/S0025-5718-1981-0595064-5
D. H. Lehmer, Strong Carmichael numbers, J. Austral. Math. Soc. Ser. A 21 (1976), no. 4, 508–510. MR 417032, DOI 10.1017/s1446788700019364
H. W. Lenstra Jr., Divisors in residue classes, Math. Comp. 42 (1984), no. 165, 331–340. MR 726007, DOI 10.1090/S0025-5718-1984-0726007-1
H. W. Lenstra Jr., Primality testing algorithms (after Adleman, Rumely and Williams), Bourbaki Seminar, Vol. 1980/81, Lecture Notes in Math., vol. 901, Springer, Berlin-New York, 1981, pp. 243–257. MR 647500
H. W. Lenstra Jr., Primality testing with Artin symbols, Number theory related to Fermat’s last theorem (Cambridge, Mass., 1981), Progr. Math., vol. 26, Birkhäuser, Boston, Mass., 1982, pp. 341–347. MR 685308
Nicos Christofides, Aristide Mingozzi, Paolo Toth, and Claudio Sandi (eds.), Combinatorial optimization, A Wiley-Interscience Publication, John Wiley & Sons, Ltd., Chichester, 1979. Lectures presented at the Summer School held in Urbino, May 30–June 11, 1977. MR 557004
Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, DOI 10.1016/S0022-0000(76)80043-8
K. Prachar, Über die Anzahl der Teiler einer natürlichen Zahl, welche die Form $p-1$ haben, Monatsh. Math. 59 (1955), 91–97 (German). MR 68569, DOI 10.1007/BF01302992
Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI 10.1016/0022-314X(80)90084-0
Jean-Pierre Serre, Cours d’arithmétique, Collection SUP: “Le Mathématicien”, vol. 2, Presses Universitaires de France, Paris, 1970 (French). MR 0255476
R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 429721, DOI 10.1137/0206006

SIGACT News

Lawrence C. Washington, Introduction to cyclotomic fields, Graduate Texts in Mathematics, vol. 83, Springer-Verlag, New York, 1982. MR 718674, DOI 10.1007/978-1-4684-0133-2
H. C. Williams, Primality testing on a computer, Ars Combin. 5 (1978), 127–185. MR 504864