×

Elliptic curves and primality proving. (English) Zbl 0792.11056

This paper describes a primality proving algorithm using the theory of elliptic curves with complex multiplication over finite fields. The algorithm is supposed to have polynomial complexity and performs well in practice. The algorithm yields a proof (or “certificate”) that the computation is correct, in the form of a list of numbers by means of which one can easily check the primality properties.
The mathematics behind the algorithm is complicated. It involves properties of quadratic forms, the theory of Hilbert class field of imaginary quadratic fields via modular forms, Weber’s functions and Dedekind’s \(\eta\) function, and elliptic curves.
Actual primality proofs are given of numbers in the 100-1500 decimal digits range. Typically, testing arbitrary integers up to 400 decimal digits can be done in a few days on a single SUN 3/60 workstation, and numbers with less than 800 digits can be done in about one week real time using about 10 workstations. The second author has made his C program available via anonymous ftp.
It is interesting to compare this algorithm with the so-called Jacobi sum test, developed by Adleman et al, and optimized by Bosma and Van der Hulst in their Doctor’s thesis project [Wieb Bosma and Marc- Paul van der Hulst, Primality proving with cyclotomy, Doctor’s thesis, University of Amsterdam (1990)]. With this test, they proved primality of the \(1065\) digit number \(n= (2^{3539}+1)/3\) at the expense of about one month computing time on a DEC-3100 workstation. They claim that their test is “substantially faster” than that of Atkin and Morain. For this number, Morain (who was the very first to prove primality of such a ‘Titanic’ prime [Advances in Cryptology, EUROCRYPT ‘90, Lect. Notes Comput. Sci. 473, 100-123 (1991; Zbl 0779.11063)]) needed a total of 319 days of CPU time on twelve SUN 3 workstations (which are about six times slower than a DEC-3100). Also for smaller numbers, Bosma and Van der Hulst claim that the Atkin and Morain’s test is inferior to their Jacobi sum test (cf. p. 264 of their thesis), but they also admit that their test does not provide a certificate of primality, contrary to Atkin and Morain’s.

MSC:

11Y11 Primality
14H52 Elliptic curves
11F11 Holomorphic modular forms of integral weight
11R37 Class field theory

Citations:

Zbl 0779.11063

Software:

BIGNUM; ECPP
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] 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.
[2] 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.
[3] 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. · Zbl 0526.10004
[4] A. O. L. Atkin, Manuscript, Lecture notes of a conference, Boulder, Colorado, August 1986.
[5] -, The number of points on an elliptic curve modulo a prime, Preprint, 1991.
[6] A. O. L. Atkin and F. Morain, Elliptic curves and primality proving. Research Report 1256, INRIA, June 1990. · Zbl 0792.11056
[7] 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. · Zbl 0815.11063
[8] R. Balasubramanian and M. R. Murty, Elliptic pseudoprimes. II, submitted for publication. · Zbl 0748.11005
[9] 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. · Zbl 0669.10014
[10] E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713 – 735. · Zbl 0247.12014
[11] W. E. H. Berwick, Modular invariants expressible in terms of quadratic and cubic irrationalities, Proc. London Math. Soc. 28 (1928), 53-69. · JFM 54.0408.01
[12] B. J. Birch, Weber’s class invariants, Mathematika 16 (1969), 283 – 294. · Zbl 0226.12005
[13] A. Borel, S. Chowla, C. S. Herz, K. Iwasawa, and J.-P. Serre, Seminar on complex multiplication, Seminar held at the Institute for Advanced Study, Princeton, N.J., 1957-58. Lecture Notes in Mathematics, No. 21, Springer-Verlag, Berlin-New York, 1966. · Zbl 0147.03902
[14] W. Bosma, Primality testing using elliptic curves, Technical Rep. 85-12, Math. Instituut, Universiteit van Amsterdam, 1985.
[15] W. Bosma and M.-P. van der Hulst, Faster primality testing, Advances in Cryptology (Proc. Eurocrypt ’89, Houthalen, April 10-13), , Lecture Notes in Comput. Sci., vol. 434, Springer-Verlag, Berlin and New York, 1990, pp. 652-656. · Zbl 0734.68046
[16] Gilles Brassard, Modern cryptology, Lecture Notes in Computer Science, vol. 325, Springer-Verlag, New York, 1988. A tutorial. · Zbl 0661.94010
[17] R. P. Brent, Some integer factorization algorithms using elliptic curves, Austral. Comp. Sci. Commun. 8 (1986), 149-163.
[18] John Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria and factorizations of 2^{\?}\pm 1, Math. Comp. 29 (1975), 620 – 647. · Zbl 0311.10009
[19] John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of \?\(^{n}\)\pm 1, 2nd ed., Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, RI, 1988. \?=2,3,5,6,7,10,11,12 up to high powers. · Zbl 0659.10001
[20] Duncan A. Buell, Small class numbers and extreme values of \?-functions of quadratic fields, Math. Comp. 31 (1977), no. 139, 786 – 796. · Zbl 0379.12001
[21] J. P. Buhler, R. E. Crandall, and M. A. Penk, Primes of the form \?!\pm 1 and 2\cdot 3\cdot 5\cdots\?\pm 1, Math. Comp. 38 (1982), no. 158, 639 – 643. · Zbl 0493.10009
[22] J. W. S. Cassels, Diophantine equations with special reference to elliptic curves, J. London Math. Soc. 41 (1966), 193 – 291. · Zbl 0138.27002
[23] 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). · Zbl 0188.35401
[24] S. Chowla, An extension of Heilbronn’s class number theorem, Quart. J. Math. Oxford 5 (1934), 304-307. · Zbl 0010.33705
[25] 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. · Zbl 0614.10004
[26] H. Cohen, Cryptographic factorisation el primalité: l’utilisation des courbes elliptiques, C. R. J. Soc. Math. France (Paris, January 1987).
[27] H. Cohen and A. K. Lenstra, Implementation of a new primality test, Math. Comp. 48 (1987), no. 177, 103 – 121, S1 – S4. · Zbl 0608.10001
[28] H. Cohen and H. W. Lenstra Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), no. 165, 297 – 330. · Zbl 0578.10004
[29] Harvey Cohn, A classical invitation to algebraic numbers and class fields, 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”; Universitext. · Zbl 0395.12001
[30] Harvey Cohn, Advanced number theory, Dover Publications, Inc., New York, 1980. Reprint of A second course in number theory, 1962; Dover Books on Advanced Mathematics. · Zbl 0208.31501
[31] Harvey Cohn, Introduction to the construction of class fields, Cambridge Studies in Advanced Mathematics, vol. 6, Cambridge University Press, Cambridge, 1985. · Zbl 0571.12001
[32] 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. · JFM 39.0258.02
[33] David A. Cox, Primes of the form \?²+\?\?², A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1989. Fermat, class field theory and complex multiplication.
[34] 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). · Zbl 0123.04001
[35] L. E. Dickson, History of the theory of numbers, vols. I, II, III, Chelsea, New York, 1952.
[36] David R. Dorman, Special values of the elliptic modular function and factorization formulae, J. Reine Angew. Math. 383 (1988), 207 – 220. · Zbl 0626.10022
[37] R. Fricke, Lehrbuch der Algebra. III, Vieweg Braunschweig, 1928. · JFM 54.0187.20
[38] Carl Friedrich Gauss, Disquisitiones arithmeticae, Translated into English by Arthur A. Clarke, S. J, Yale University Press, New Haven, Conn.-London, 1966. · Zbl 0136.32301
[39] K. Girstmair, Über die praktische Auflösung von Gleichungen höheren Grades, Mathematische Semesterberichte, Band XXXIV/1987, Heft 2 (1987), 213-245. · Zbl 0633.12011
[40] 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.
[41] Daniel M. Gordon, On the number of elliptic pseudoprimes, Math. Comp. 52 (1989), no. 185, 231 – 245. · Zbl 0658.10005
[42] A. G. Greenhill, Table of complex multiplication moduli, Proc. London Math. Soc. (1) 21 (1891), 403-422. · JFM 22.0467.01
[43] 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. · Zbl 0433.14032
[44] Benedict H. Gross and Don B. Zagier, On singular moduli, J. Reine Angew. Math. 355 (1985), 191 – 220. · Zbl 0545.10015
[45] 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.
[46] 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.
[47] -, Riemann hypothesis and finding roots over finite fields, Proc. 17th ACM STOC (1985), ACM, New York, 1985, pp. 121-130
[48] 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. · Zbl 0482.10001
[49] 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.
[50] 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. · Zbl 0583.12007
[51] -, 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.
[52] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0477.65002
[53] Serge Lang, Elliptic functions, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Amsterdam, 1973. With an appendix by J. Tate. · Zbl 0316.14001
[54] A. K. Lenstra and H. W. Lenstra, Jr., Algorithms in number theory, Handbook of Theoretical Computer Science, vol. A: Algorithms and Complexity , North-Holland, Amsterdam and New York, 1990, pp. 674-715. · Zbl 0900.68250
[55] 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.
[56] H. W. Lenstra, Jr., Elliptic curves and number theoretic algorithms, Tech. Rep. Report 86-19, Math. Inst., Univ. Amsterdam, 1986.
[57] H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649 – 673. · Zbl 0629.10006
[58] 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). · Zbl 0621.14021
[59] J.-F. Mestre and V. S. Miller, Computing j via \( {X_0}(N)\), in preparation, March 1990.
[60] 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. · Zbl 0686.10001
[61] I. Miyamoto and M. Ram Murty, Elliptic pseudoprimes, Math. Comp. 53 (1989), no. 187, 415 – 430. · Zbl 0697.14021
[62] Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243 – 264. · Zbl 0608.10005
[63] F. Morain, Implementation of the Atkin-Goldwasser-Kilian primality testing algorithm, Rapport de Recherche 911, INRIA, Octobre 1988.
[64] -, Construction of Hilbert class fields of imaginary quadratic fields and dihedral equations modulo p, Rapport de Recherche 1087, INRIA, Septembre 1989.
[65] -, Résolution d’équations de petit degré modulo de grands nombres premiers, Rapport de Recherche 1085, INRIA, Septembre 1989.
[66] -, Solving generalized dihedral equations, Manuscript, August 1990.
[67] -, 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), , Lecture Notes in Comput. Sci., vol. 473, Springer-Verlag, Berlin and New York, 1991, pp. 110-123. · Zbl 0779.11063
[68] 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). · Zbl 0760.11041
[69] -, Prime values of partition numbers and the primality of \( p(1840926)\), preprint, August 1992.
[70] F. Morain and J. Nicolas, On Cornacchia’s algorithm, manuscript, March 1990.
[71] 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). · Zbl 0724.11068
[72] 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. · Zbl 0365.20025
[73] Andrew Ogg, Modular forms and Dirichlet series, W. A. Benjamin, Inc., New York-Amsterdam, 1969. · Zbl 0191.38101
[74] A. R. Rajwade and J. C. Parnami, A new cubic character sum, Acta Arith. 40 (1981/82), no. 4, 347 – 356. · Zbl 0488.10036
[75] Carl Pomerance, Very short primality proofs, Math. Comp. 48 (1987), no. 177, 315 – 322. · Zbl 0608.10002
[76] Dimitrios Poulakis, Évaluation d’une somme cubique de caractères, J. Number Theory 27 (1987), no. 1, 41 – 45 (French). · Zbl 0619.10035
[77] Vaughan R. Pratt, Every prime has a succinct certificate, SIAM J. Comput. 4 (1975), no. 3, 214 – 220. · Zbl 0316.68031
[78] A. R. Rajwade, Certain classical congruences via elliptic curves, J. London Math. Soc. (2) 8 (1974), 60 – 62. · Zbl 0277.10028
[79] A. R. Rajwade, The Diophantine equation \?²=\?(\?²+21\?\?+112\?²) and the conjectures of Birch and Swinnerton-Dyer, J. Austral. Math. Soc. Ser. A 24 (1977), no. 3, 286 – 295. · Zbl 0382.14006
[80] Paulo Ribenboim, The book of prime number records, 2nd ed., Springer-Verlag, New York, 1989. · Zbl 0642.10001
[81] Neil W. Rickert, Efficient reduction of quadratic forms, Computers and mathematics (Cambridge, MA, 1989) Springer, New York, 1989, pp. 135 – 139. · Zbl 0678.10018
[82] Reinhard Schertz, Die singulären Werte der Weberschen Funktionen \?,\?\?\?1,\?\(_{2}\), \?\(_{2}\), \?\(_{3}\), J. Reine Angew. Math. 286/287 (1976), 46 – 74 (German). · Zbl 0335.12018
[83] René Schoof, Elliptic curves over finite fields and the computation of square roots mod \?, Math. Comp. 44 (1985), no. 170, 483 – 494. · Zbl 0579.14025
[84] Jean-Pierre Serre, Cours d’arithmétique, Collection SUP: ”Le Mathématicien”, vol. 2, Presses Universitaires de France, Paris, 1970 (French). · Zbl 0376.12001
[85] 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.
[86] Daniel Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Utilitas Math., Winnipeg, Man., 1973, pp. 51 – 70. Congressus Numerantium, No. VII.
[87] 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, The Mathematical Society of Japan, Tokyo, 1961. · Zbl 0112.03502
[88] H. M. Stark, On the ”gap” in a theorem of Heegner, J. Number Theory 1 (1969), 16 – 27. · Zbl 0198.37702
[89] 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. · Zbl 0602.10022
[90] G. N. Watson, Ramanujans Vermutung über Zerfällungsanzahlen, J. Reine Angew. Math. 179 (1938), 97-128. · Zbl 0019.15302
[91] H. Weber, Lehrbuch der Algebra, vols. I, II, III, Chelsea, New York, 1902.
[92] H. C. Williams, Primality testing on a computer, Ars Combin. 5 (1978), 127 – 185. · Zbl 0406.10008
[93] H. C. Williams, Some primes with interesting digit patterns, Math. Comp. 32 (1978), no. 144, 1306 – 1310. · Zbl 0388.10007
[94] H. C. Williams, Effective primality tests for some integers of the forms \?5\(^{n}\)-1 and \?7\(^{n}\)-1, Math. Comp. 48 (1987), no. 177, 385 – 403. · Zbl 0608.10003
[95] H. C. Williams and Harvey Dubner, The primality of \?1031, Math. Comp. 47 (1986), no. 176, 703 – 711. · Zbl 0602.10001
[96] H. C. Williams and C. R. Zarnke, Some algorithms for solving a cubic congruence modulo \?, Utilitas Math. 6 (1974), 285 – 306. · Zbl 0294.10001
[97] M. C. Wunderlich, A performance analysis of a simple prime-testing algorithm, Math. Comp. 40 (1983), no. 162, 709 – 714. · Zbl 0517.10002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.