Elliptic curves and primality proving
HTML articles powered by AMS MathViewer
- by A. O. L. Atkin and F. Morain PDF
- Math. Comp. 61 (1993), 29-68 Request permission
Abstract:
The aim of this paper is to describe the theory and implementation of the Elliptic Curve Primality Proving algorithm. Problema, numeros primos a compositis dignoscendi, hosque in factores suos primos resolvendi, ad gravissima ac utilissima totius arithmeticae pertinere, et geometrarum tum veterum tum recentiorum industriam ac sagacitatem occupavisse, tam notum est, ut de hac re copiose loqui superfluum foret.References
- Leonard Adleman, Kenneth Manders, and Gary Miller, On taking roots in finite fields, 18th Annual Symposium on Foundations of Computer Science (Providence, R.I., 1977) IEEE Comput. Sci., Long Beach, Calif., 1977, pp. 175–178. MR 0502224 L. M. Adleman and M. A. Huang, Recognizing primes in random polynomial time, Proc. 19th STOC (New York City, May 25-27, 1986), ACM Press, New York, 1987, pp. 462-469.
- 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 A. O. L. Atkin, Manuscript, Lecture notes of a conference, Boulder, Colorado, August 1986. —, The number of points on an elliptic curve modulo a prime, Preprint, 1991. A. O. L. Atkin and F. Morain, Elliptic curves and primality proving. Research Report 1256, INRIA, June 1990.
- A. O. L. Atkin and F. Morain, Finding suitable curves for the elliptic curve method of factorization, Math. Comp. 60 (1993), no. 201, 399–405. MR 1140645, DOI 10.1090/S0025-5718-1993-1140645-1 R. Balasubramanian and M. R. Murty, Elliptic pseudoprimes. II, submitted for publication.
- Pierre Beauchemin, Gilles Brassard, Claude Crépeau, Claude Goutier, and Carl Pomerance, The generation of random numbers that are probably prime, J. Cryptology 1 (1988), no. 1, 53–64. MR 935901, DOI 10.1007/BF00206325
- E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, DOI 10.1090/S0025-5718-1970-0276200-X W. E. H. Berwick, Modular invariants expressible in terms of quadratic and cubic irrationalities, Proc. London Math. Soc. 28 (1928), 53-69.
- B. J. Birch, Weber’s class invariants, Mathematika 16 (1969), 283–294. MR 262206, DOI 10.1112/S0025579300008251
- A. Borel, S. Chowla, C. S. Herz, K. Iwasawa, and J.-P. Serre, Seminar on complex multiplication, Lecture Notes in Mathematics, No. 21, Springer-Verlag, Berlin-New York, 1966. Seminar held at the Institute for Advanced Study, Princeton, N.J., 1957-58. MR 0201394 W. Bosma, Primality testing using elliptic curves, Technical Rep. 85-12, Math. Instituut, Universiteit van Amsterdam, 1985. W. Bosma and M.-P. van der Hulst, Faster primality testing, Advances in Cryptology (Proc. Eurocrypt ’89, Houthalen, April 10-13), (J.-J. Quisquater, ed.), Lecture Notes in Comput. Sci., vol. 434, Springer-Verlag, Berlin and New York, 1990, pp. 652-656.
- Gilles Brassard, Modern cryptology, Lecture Notes in Computer Science, vol. 325, Springer-Verlag, New York, 1988. A tutorial. MR 962639 R. P. Brent, Some integer factorization algorithms using elliptic curves, Austral. Comp. Sci. Commun. 8 (1986), 149-163.
- 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
- John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of $b^n \pm 1$, 2nd ed., Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, RI, 1988. $b=2,3,5,6,7,10,11,12$ up to high powers. MR 996414, DOI 10.1090/conm/022
- Duncan A. Buell, Small class numbers and extreme values of $L$-functions of quadratic fields, Math. Comp. 31 (1977), no. 139, 786–796. MR 439802, DOI 10.1090/S0025-5718-1977-0439802-X
- J. P. Buhler, R. E. Crandall, and M. A. Penk, Primes of the form $n!\pm 1$ and $2\cdot 3\cdot 5\cdots p\pm 1$, Math. Comp. 38 (1982), no. 158, 639–643. MR 645679, DOI 10.1090/S0025-5718-1982-0645679-1
- J. W. S. Cassels, Diophantine equations with special reference to elliptic curves, J. London Math. Soc. 41 (1966), 193–291. MR 199150, DOI 10.1112/jlms/s1-41.1.193
- Danièle Chatelain, Bases normales de l’anneau des entiers de certaines extensions abéliennes de Q, C. R. Acad. Sci. Paris Sér. A-B 270 (1970), A557–A560 (French). MR 258802 S. Chowla, An extension of Heilbronn’s class number theorem, Quart. J. Math. Oxford 5 (1934), 304-307. D. V. Chudnovsky and G. V. Chudnovsky, Sequences of numbers generated by addition in formal groups and new primality and factorization tests, Research report RC 11262, IBM, Yorktown Heights, NY, 1985. H. Cohen, Cryptographic factorisation el primalité: l’utilisation des courbes elliptiques, C. R. J. Soc. Math. France (Paris, January 1987).
- H. Cohen and A. K. Lenstra, Implementation of a new primality test, Math. Comp. 48 (1987), no. 177, 103–121, S1–S4. MR 866102, DOI 10.1090/S0025-5718-1987-0866102-2
- H. Cohen and H. W. Lenstra Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), no. 165, 297–330. MR 726006, DOI 10.1090/S0025-5718-1984-0726006-X
- Harvey Cohn, A classical invitation to algebraic numbers and class fields, Universitext, Springer-Verlag, New York-Heidelberg, 1978. With two appendices by Olga Taussky: “Artin’s 1932 Göttingen lectures on class field theory” and “Connections between algebraic number theory and integral matrices”. MR 506156
- Harvey Cohn, Advanced number theory, Dover Books on Advanced Mathematics, Dover Publications, Inc., New York, 1980. Reprint of A second course in number theory, 1962. MR 594936
- Harvey Cohn, Introduction to the construction of class fields, Cambridge Studies in Advanced Mathematics, vol. 6, Cambridge University Press, Cambridge, 1985. MR 812270 G. Cornacchia, Su di un metodo per la risoluzione in numeri interi dell’ equazione $\sum _{h = 0}^n{C_h}{x^{n - h}}{y^h} = P$, G. Mat. Battaglini 46 (1908), 33-90.
- David A. Cox, Primes of the form $x^2 + ny^2$, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1989. Fermat, class field theory and complex multiplication. MR 1028322
- M. Deuring, Die Klassenkörper der komplexen Multiplikation, Enzyklopädie der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen, Band I 2, Heft 10, Teil II (Article I 2, vol. 23, B. G. Teubner Verlagsgesellschaft, Stuttgart, 1958 (German). MR 0167481 L. E. Dickson, History of the theory of numbers, vols. I, II, III, Chelsea, New York, 1952.
- David R. Dorman, Special values of the elliptic modular function and factorization formulae, J. Reine Angew. Math. 383 (1988), 207–220. MR 921991, DOI 10.1515/crll.1988.383.207 R. Fricke, Lehrbuch der Algebra. III, Vieweg Braunschweig, 1928.
- Carl Friedrich Gauss, Disquisitiones arithmeticae, Yale University Press, New Haven, Conn.-London, 1966. Translated into English by Arthur A. Clarke, S. J. MR 0197380 K. Girstmair, Über die praktische Auflösung von Gleichungen höheren Grades, Mathematische Semesterberichte, Band XXXIV/1987, Heft 2 (1987), 213-245. S. Goldwasser and J. Kilian, Almost all primes can be quickly certified, Proc. 18th STOC (Berkeley, May 28-30, 1986), ACM, New York, 1986, pp. 316-329.
- Daniel M. Gordon, On the number of elliptic pseudoprimes, Math. Comp. 52 (1989), no. 185, 231–245. MR 946604, DOI 10.1090/S0025-5718-1989-0946604-2 A. G. Greenhill, Table of complex multiplication moduli, Proc. London Math. Soc. (1) 21 (1891), 403-422.
- Benedict H. Gross, Arithmetic on elliptic curves with complex multiplication, Lecture Notes in Mathematics, vol. 776, Springer, Berlin, 1980. With an appendix by B. Mazur. MR 563921
- Benedict H. Gross and Don B. Zagier, On singular moduli, J. Reine Angew. Math. 355 (1985), 191–220. MR 772491 J.-C. Hervé, F. Morain, D. Salesin, B. Serpette, J. Vuillemin, and P. Zimmermann, Bignum: A portable and efficient package for arbitrary precision arithmetic, Rapport de Recherche 1016, INRIA, avril 1989. M.-D. A. Huang, Factorization of polynomials over finite fields and factorization of primes in algebraic number fields, Proc. 16th ACM STOC (1984), ACM, New York, 1984, pp. 175-182. —, Riemann hypothesis and finding roots over finite fields, Proc. 17th ACM STOC (1985), ACM, New York, 1985, pp. 121-130
- Kenneth F. Ireland and Michael I. Rosen, A classical introduction to modern number theory, Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York-Berlin, 1982. Revised edition of Elements of number theory. MR 661047 E. Kaltofen, T. Valente, and N. Yui, An improved Las Vegas primality test, Research Report 89-12, Rensselaer Polytechnic Inst., Troy, New York, May 1989.
- Erich Kaltofen and Noriko Yui, Explicit construction of the Hilbert class fields of imaginary quadratic fields with class numbers $7$ and $11$, EUROSAM 84 (Cambridge, 1984) Lecture Notes in Comput. Sci., vol. 174, Springer, Berlin, 1984, pp. 310–320. MR 779136, DOI 10.1007/BFb0032853 —, Explicit construction of the Hilbert class fields of imaginary quadratic fields by integer lattice reduction, Research Report 89-13, Rensselaer Polytechnic Inst., Troy, New York, May 1989.
- 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
- Serge Lang, Elliptic functions, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Amsterdam, 1973. With an appendix by J. Tate. MR 0409362 A. K. Lenstra and H. W. Lenstra, Jr., Algorithms in number theory, Handbook of Theoretical Computer Science, vol. A: Algorithms and Complexity (J. van Leeuwen, ed.), North-Holland, Amsterdam and New York, 1990, pp. 674-715.
- Arjen K. Lenstra and Mark S. Manasse, Factoring by electronic mail, Advances in cryptology—EUROCRYPT ’89 (Houthalen, 1989) Lecture Notes in Comput. Sci., vol. 434, Springer, Berlin, 1990, pp. 355–371. MR 1083962, DOI 10.1007/3-540-46885-4_{3}5 H. W. Lenstra, Jr., Elliptic curves and number theoretic algorithms, Tech. Rep. Report 86-19, Math. Inst., Univ. Amsterdam, 1986.
- H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
- J.-F. Mestre, La méthode des graphes. Exemples et applications, Proceedings of the international conference on class numbers and fundamental units of algebraic number fields (Katata, 1986) Nagoya Univ., Nagoya, 1986, pp. 217–242 (French). MR 891898 J.-F. Mestre and V. S. Miller, Computing j via ${X_0}(N)$, in preparation, March 1990.
- Preda Mihailescu, A primality test using cyclotomic extensions, Applied algebra, algebraic algorithms and error-correcting codes (Rome, 1988) Lecture Notes in Comput. Sci., vol. 357, Springer, Berlin, 1989, pp. 310–323. MR 1008509, DOI 10.1007/3-540-51083-4_{6}8
- I. Miyamoto and M. Ram Murty, Elliptic pseudoprimes, Math. Comp. 53 (1989), no. 187, 415–430. MR 970701, DOI 10.1090/S0025-5718-1989-0970701-9
- Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243–264. MR 866113, DOI 10.1090/S0025-5718-1987-0866113-7 F. Morain, Implementation of the Atkin-Goldwasser-Kilian primality testing algorithm, Rapport de Recherche 911, INRIA, Octobre 1988. —, Construction of Hilbert class fields of imaginary quadratic fields and dihedral equations modulo p, Rapport de Recherche 1087, INRIA, Septembre 1989. —, Résolution d’équations de petit degré modulo de grands nombres premiers, Rapport de Recherche 1085, INRIA, Septembre 1989. —, Solving generalized dihedral equations, Manuscript, August 1990. —, Distributed primality proving and the primality of $({2^{3539}} + 1)/3$, Advances in Cryptology—EUROCRYPT ’90 (Proc. Workshop on the Theory and Appl. of Cryptographic Techniques, Aarhus, Denmark, May 21-24, 1990), (I. B. Damgård, ed.), Lecture Notes in Comput. Sci., vol. 473, Springer-Verlag, Berlin and New York, 1991, pp. 110-123.
- François Morain, Elliptic curves, primality proving and some titanic primes, Astérisque 198-200 (1991), 245–251 (1992). Journées Arithmétiques, 1989 (Luminy, 1989). MR 1144327 —, Prime values of partition numbers and the primality of $p(1840926)$, preprint, August 1992. F. Morain and J. Nicolas, On Cornacchia’s algorithm, manuscript, March 1990.
- François Morain and Jorge Olivos, Speeding up the computations on an elliptic curve using addition-subtraction chains, RAIRO Inform. Théor. Appl. 24 (1990), no. 6, 531–543 (English, with French summary). MR 1082914, DOI 10.1051/ita/1990240605311
- Morris Newman, Daniel Shanks, and H. C. Williams, Simple groups of square order and an interesting sequence of primes, Acta Arith. 38 (1980/81), no. 2, 129–140. MR 604229, DOI 10.4064/aa-38-2-129-140
- Andrew Ogg, Modular forms and Dirichlet series, W. A. Benjamin, Inc., New York-Amsterdam, 1969. MR 0256993
- A. R. Rajwade and J. C. Parnami, A new cubic character sum, Acta Arith. 40 (1981/82), no. 4, 347–356. MR 667045, DOI 10.4064/aa-40-4-347-356
- Carl Pomerance, Very short primality proofs, Math. Comp. 48 (1987), no. 177, 315–322. MR 866117, DOI 10.1090/S0025-5718-1987-0866117-4
- Dimitrios Poulakis, Évaluation d’une somme cubique de caractères, J. Number Theory 27 (1987), no. 1, 41–45 (French). MR 904006, DOI 10.1016/0022-314X(87)90049-7
- Vaughan R. Pratt, Every prime has a succinct certificate, SIAM J. Comput. 4 (1975), no. 3, 214–220. MR 391574, DOI 10.1137/0204018
- A. R. Rajwade, Certain classical congruences via elliptic curves, J. London Math. Soc. (2) 8 (1974), 60–62. MR 338001, DOI 10.1112/jlms/s2-8.1.60
- A. R. Rajwade, The Diophantine equation $y^{2}=x(x^{2}+21Dx+112D^{2})$ and the conjectures of Birch and Swinnerton-Dyer, J. Austral. Math. Soc. Ser. A 24 (1977), no. 3, 286–295. MR 472828, DOI 10.1017/s1446788700020309
- Paulo Ribenboim, The book of prime number records, 2nd ed., Springer-Verlag, New York, 1989. MR 1016815, DOI 10.1007/978-1-4684-0507-1
- Neil W. Rickert, Efficient reduction of quadratic forms, Computers and mathematics (Cambridge, MA, 1989) Springer, New York, 1989, pp. 135–139. MR 1005969, DOI 10.1007/978-1-4613-9647-5_{1}7
- Reinhard Schertz, Die singulären Werte der Weberschen Funktionen $\mathfrak {f},\mathfrak {f}sb{1},\mathfrak {f}_{2},$ $\gamma _{2},$ $\gamma _{3}$, J. Reine Angew. Math. 286(287) (1976), 46–74 (German). MR 422213, DOI 10.1515/crll.1976.286-287.46
- René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, DOI 10.1090/S0025-5718-1985-0777280-6
- Jean-Pierre Serre, Cours d’arithmétique, Collection SUP: “Le Mathématicien”, vol. 2, Presses Universitaires de France, Paris, 1970 (French). MR 0255476
- Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385
- Daniel Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Congressus Numerantium, No. VII, Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. MR 0371855
- Goro Shimura and Yutaka Taniyama, Complex multiplication of abelian varieties and its applications to number theory, Publications of the Mathematical Society of Japan, vol. 6, Mathematical Society of Japan, Tokyo, 1961. MR 0125113
- H. M. Stark, On the “gap” in a theorem of Heegner, J. Number Theory 1 (1969), 16–27. MR 241384, DOI 10.1016/0022-314X(69)90023-7 B. Vallée, Une approche géométrique des algorithmes de réduction des réseaux en petite dimension, Thèse, Université de Caen, 1986. G. N. Watson, Ramanujans Vermutung über Zerfällungsanzahlen, J. Reine Angew. Math. 179 (1938), 97-128. H. Weber, Lehrbuch der Algebra, vols. I, II, III, Chelsea, New York, 1902.
- H. C. Williams, Primality testing on a computer, Ars Combin. 5 (1978), 127–185. MR 504864
- H. C. Williams, Some primes with interesting digit patterns, Math. Comp. 32 (1978), no. 144, 1306–1310. MR 480311, DOI 10.1090/S0025-5718-1978-0480311-0
- H. C. Williams, Effective primality tests for some integers of the forms $A5^n-1$ and $A7^n-1$, Math. Comp. 48 (1987), no. 177, 385–403. MR 866123, DOI 10.1090/S0025-5718-1987-0866123-X
- H. C. Williams and Harvey Dubner, The primality of $R1031$, Math. Comp. 47 (1986), no. 176, 703–711. MR 856714, DOI 10.1090/S0025-5718-1986-0856714-3
- H. C. Williams and C. R. Zarnke, Some algorithms for solving a cubic congruence modulo $p$, Utilitas Math. 6 (1974), 285–306. MR 389730
- M. C. Wunderlich, A performance analysis of a simple prime-testing algorithm, Math. Comp. 40 (1983), no. 162, 709–714. MR 689483, DOI 10.1090/S0025-5718-1983-0689483-8
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Math. Comp. 61 (1993), 29-68
- MSC: Primary 11Y11; Secondary 11F11, 11G20, 11R37
- DOI: https://doi.org/10.1090/S0025-5718-1993-1199989-X
- MathSciNet review: 1199989