Modular polynomials via isogeny volcanoes. (English) Zbl 1267.11125
Summary: We present a new algorithm to compute the classical modular polynomial \(\Phi_l\) in the rings \(\mathbb Z[X,Y]\) and \((\mathbb Z/m\mathbb Z)[X,Y]\), for a prime \(l\) and any positive integer \(m\). Our approach uses the graph of \(l\)-isogenies to efficiently compute \(\Phi_l\bmod p\) for many primes \(p\) of a suitable form, and then applies the Chinese Remainder Theorem (CRT). Under the Generalized Riemann Hypothesis (GRH), we achieve an expected running time of \(O(l^3 (\log l)^3\log\log l)\), and compute \(\Phi_l\bmod m\) using \(O(l^2(\log l)^2+ l^2\log m)\) space. We have used the new algorithm to compute \(\Phi_l\) with \(l\) over 5000, and \(\Phi_l\bmod m\) with \( l\) over \(20\,000\). We also consider several modular functions \(g\) for which \(\Phi_l^g\) is smaller than \(\Phi_l\), allowing us to handle \(l\) over \(60\,000\).
MSC:
| 11Y16 | Number-theoretic algorithms; complexity |
| 11G15 | Complex multiplication and moduli of abelian varieties |
| 11G20 | Curves over finite and local fields |
References:
| [1] | Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355 – 380. · Zbl 0701.11075 |
| [2] | Juliana Belding, Reinier Bröker, Andreas Enge, and Kristin Lauter, Computing Hilbert class polynomials, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 5011, Springer, Berlin, 2008, pp. 282 – 295. · Zbl 1205.11139 · doi:10.1007/978-3-540-79456-1_19 |
| [3] | E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713 – 735. · Zbl 0247.12014 |
| [4] | Daniel J. Bernstein and Jonathan P. Sorenson, Modular exponentiation via the explicit Chinese remainder theorem, Math. Comp. 76 (2007), no. 257, 443 – 454. · Zbl 1183.11080 |
| [5] | Ingrid Biehl and Johannes Buchmann, An analysis of the reduction algorithms for binary quadratic forms, Voronoi’s Impact on Modern Science , Institute of Mathematics, Kyiv, 1998, available at http://www.cdc.informatik.tu-darmstadt. de/reports/TR/TI-97-26.ps.gz, pp. 71-98. · Zbl 0948.11051 |
| [6] | Gaetan Bisson and Andrew V. Sutherland, Computing the endomorphism ring of an ordinary elliptic curve over a finite field, J. Number Theory 131 (2011), no. 5, 815 – 831. · Zbl 1225.11085 · doi:10.1016/j.jnt.2009.11.003 |
| [7] | I. F. Blake, G. Seroussi, and N. P. Smart, Elliptic curves in cryptography, London Mathematical Society Lecture Note Series, vol. 265, Cambridge University Press, Cambridge, 2000. Reprint of the 1999 original. · Zbl 0937.94008 |
| [8] | Ian F. Blake, János A. Csirik, Michael Rubinstein, and Gadiel Seroussi, On the computation of modular polynomials for elliptic curves, Tech. report, Hewlett-Packard Laboratories, 1999, http://www.math.uwaterloo.ca/ mrubinst/publications/publications.html. |
| [9] | A. Bostan, F. Morain, B. Salvy, and É. Schost, Fast algorithms for computing isogenies between elliptic curves, Math. Comp. 77 (2008), no. 263, 1755 – 1778. · Zbl 1200.11097 |
| [10] | Reinier Bröker, Constructing elliptic curves of prescribed order, PhD thesis, Universiteit Leiden, 2006. · Zbl 1162.11028 |
| [11] | Reinier Bröker, A \?-adic algorithm to compute the Hilbert class polynomial, Math. Comp. 77 (2008), no. 264, 2417 – 2435. · Zbl 1223.11073 |
| [12] | -, \( p\)-adic class invariants, LMS Journal of Computation and Mathematics (2010), to appear. |
| [13] | Reinier Bröker and Andrew V. Sutherland, An explicit height bound for the classical modular polynomial, Ramanujan J. 22 (2010), no. 3, 293 – 313. · Zbl 1245.11079 · doi:10.1007/s11139-010-9231-8 |
| [14] | Johannes Buchmann and Ulrich Vollmer, Binary quadratic forms, Algorithms and Computation in Mathematics, vol. 20, Springer, Berlin, 2007. An algorithmic approach. · Zbl 1125.11028 |
| [15] | J.J. Cannon and W. Bosma , Handbook of Magma functions, 2.15 ed., 2008, available at http://magma.maths.usyd.edu.au/magma/htmlhelp/MAGMA.htm. |
| [16] | Guilhem Castagnos and Fabien Laguillaumie, On the security of cryptosystems with quadratic decryption: the nicest cryptanalysis, Advances in cryptology — EUROCRYPT 2009, Lecture Notes in Comput. Sci., vol. 5479, Springer, Berlin, 2009, pp. 260 – 277. · Zbl 1239.94041 · doi:10.1007/978-3-642-01001-9_15 |
| [17] | Denis Charles and Kristin Lauter, Computing modular polynomials, LMS J. Comput. Math. 8 (2005), 195 – 204. · Zbl 1119.11030 · doi:10.1112/S1461157000000954 |
| [18] | Henri Cohen, Advanced topics in computational number theory, Graduate Texts in Mathematics, vol. 193, Springer-Verlag, New York, 2000. · Zbl 0977.11056 |
| [19] | Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren , Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006. · Zbl 1082.94001 |
| [20] | Paula Cohen, On the coefficients of the transformation polynomials for the elliptic modular function, Math. Proc. Cambridge Philos. Soc. 95 (1984), no. 3, 389 – 402. · Zbl 0541.10026 · doi:10.1017/S0305004100061697 |
| [21] | 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. |
| [22] | Noam D. Elkies, Elliptic and modular curves over finite fields and related computational issues, Computational perspectives on number theory (Chicago, IL, 1995) AMS/IP Stud. Adv. Math., vol. 7, Amer. Math. Soc., Providence, RI, 1998, pp. 21 – 76. · Zbl 0915.11036 |
| [23] | Andreas Enge, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), no. 266, 1089 – 1107. · Zbl 1208.11136 |
| [24] | Andreas Enge, Computing modular polynomials in quasi-linear time, Math. Comp. 78 (2009), no. 267, 1809 – 1824. · Zbl 1215.11121 |
| [25] | Andreas Enge and Francois Morain, Generalized Weber functions I, 2009, http://arxiv.org/ abs/0905.3250. |
| [26] | Andreas Enge and Reinhard Schertz, Constructing elliptic curves over finite fields using double eta-quotients, J. Théor. Nombres Bordeaux 16 (2004), no. 3, 555 – 568 (English, with English and French summaries). · Zbl 1072.11039 |
| [27] | Andreas Enge and Reinhard Schertz, Modular curves of composite level, Acta Arith. 118 (2005), no. 2, 129 – 141. · Zbl 1158.11322 · doi:10.4064/aa118-2-3 |
| [28] | Andreas Enge and Andrew V. Sutherland, Class invariants for the CRT method, Algorithmic Number Theory Symposium-ANTS IX , Lecture Notes in Computer Science, vol. 6197, Springer-Verlag, 2010, pp. 142-156. · Zbl 1260.11083 |
| [29] | Free Software Foundation, GNU compiler collection, January 2010, version 4.4.3, available at http://gcc.gnu.org/. |
| [30] | Mireille Fouquet and François Morain, Isogeny volcanoes and the SEA algorithm, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 276 – 291. · Zbl 1058.11041 · doi:10.1007/3-540-45455-1_23 |
| [31] | Steven D. Galbraith, Florian Hess, and Nigel P. Smart, Extending the GHS Weil descent attack, Advances in cryptology — EUROCRYPT 2002 (Amsterdam), Lecture Notes in Comput. Sci., vol. 2332, Springer, Berlin, 2002, pp. 29 – 44. · Zbl 1055.94013 · doi:10.1007/3-540-46035-7_3 |
| [32] | Alice Gee and Peter Stevenhagen, Generating class fields using Shimura reciprocity, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 441 – 453. · Zbl 0912.11045 · doi:10.1007/BFb0054883 |
| [33] | Torbjörn Granlund et al., GNU multiple precision arithmetic library, September 2010, version 5.0.1, available at http://gmplib.org/. |
| [34] | G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, Oxford, at the Clarendon Press, 1954. 3rd ed. · Zbl 0058.03301 |
| [35] | David Harvey, \(\text{zn\_poly}\): a library for polynomial arithmetic, 2008, version 0.9, http://cims. nyu.edu/ harvey/zn_poly. |
| [36] | David Harvey, Faster polynomial multiplication via multipoint Kronecker substitution, J. Symbolic Comput. 44 (2009), no. 10, 1502 – 1510. · Zbl 1194.68265 · doi:10.1016/j.jsc.2009.05.004 |
| [37] | Oskar Herrmann, Über die Berechnung der Fourierkoeffizienten der Funktion \?(\?), J. Reine Angew. Math. 274/275 (1975), 187 – 195 (German). Collection of articles dedicated to Helmut Hasse on his seventy-fifth birthday, III. · Zbl 0312.10014 · doi:10.1515/crll.1975.274-275.187 |
| [38] | Derek F. Holt, Bettina Eick, and Eamonn A. O’Brien, Handbook of computational group theory, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2005. · Zbl 1091.20001 |
| [39] | Hideji Ito, Computation of the modular equation, Proc. Japan Acad. Ser. A Math. Sci. 71 (1995), no. 3, 48 – 50. · Zbl 0832.11017 |
| [40] | M. Jarden, Transfer principles for finite and \?-adic fields, Nieuw Arch. Wisk. (3) 28 (1980), no. 2, 139 – 158. · Zbl 0446.12022 |
| [41] | Erich Kaltofen and Noriko Yui, On the modular equation of order \( 11\), Proceedings of the 1984 MACSYMA Users Conference, 1984, pp. 472-485. · Zbl 0583.12007 |
| [42] | David Russell Kohel, Endomorphism rings of elliptic curves over finite fields, ProQuest LLC, Ann Arbor, MI, 1996. Thesis (Ph.D.) – University of California, Berkeley. |
| [43] | J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: \?-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409 – 464. · Zbl 0362.12011 |
| [44] | Serge Lang, Elliptic functions, 2nd ed., Graduate Texts in Mathematics, vol. 112, Springer-Verlag, New York, 1987. With an appendix by J. Tate. · Zbl 0615.14018 |
| [45] | Frank Lehmann, Markus Maurer, Volker Müller, and Victor Shoup, Counting the number of points on elliptic curves over finite fields of characteristic greater than three, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 60 – 70. · Zbl 0839.11026 · doi:10.1007/3-540-58691-1_44 |
| [46] | H. W. Lenstra Jr. and Carl Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), no. 3, 483 – 516. · Zbl 0770.11057 |
| [47] | François Morain, Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques, J. Théor. Nombres Bordeaux 7 (1995), no. 1, 255 – 282 (French, with English and French summaries). Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). · Zbl 0843.11030 |
| [48] | Volker Müller, Ein Algorithmus zur Bestimmung der Punktanzahl elliptischer Kurven über endlichen Körpern der Charakteristik größer drei, PhD thesis, Universität des Saarlandes, 1995. |
| [49] | Jürgen Neukirch, Algebraic number theory, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 322, Springer-Verlag, Berlin, 1999. Translated from the 1992 German original and with a note by Norbert Schappacher; With a foreword by G. Harder. · Zbl 0956.11021 |
| [50] | A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281 – 292 (German, with English summary). · Zbl 0223.68007 |
| [51] | René Schoof, Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1995), no. 1, 219 – 254. Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). · Zbl 0852.11073 |
| [52] | William Stein and David Joyner, SAGE: System for Algebra and Geometry Experimentation, Communications in Computer Algebra (SIGSAM Bulletin) (2005), 61-64. · Zbl 1341.68315 |
| [53] | Peter Stevenhagen, The arithmetic of number rings, Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 209 – 266. · Zbl 1216.11099 |
| [54] | Andrew V. Sutherland, Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comp. 80 (2011), no. 273, 501 – 538. · Zbl 1231.11144 |
| [55] | Jacques Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A238 – A241 (French). · Zbl 0225.14014 |
| [56] | Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. · Zbl 1055.68168 |
| [57] | Lawrence C. Washington, Elliptic curves, 2nd ed., Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2008. Number theory and cryptography. · Zbl 1200.11043 |
| [58] | Heinrich Weber, Lehrbuch der algebra, third ed., vol. III, Chelsea, 1961. |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
