Modular polynomials via isogeny volcanoes

Bröker, Reinier; Lauter, Kristin; Sutherland, Andrew

doi:10.1090/S0025-5718-2011-02508-1

Modular polynomials via isogeny volcanoes
HTML articles powered by AMS MathViewer

by Reinier Bröker, Kristin Lauter and Andrew V. Sutherland;

Math. Comp. 81 (2012), 1201-1231

DOI: https://doi.org/10.1090/S0025-5718-2011-02508-1

Published electronically: July 14, 2011

PDF | Request permission

Abstract:

We present a new algorithm to compute the classical modular polynomial $\Phi _l$ in the rings $\mathbf {Z}[X,Y]$ and $(\mathbf {Z}/m\mathbf {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 20000. We also consider several modular functions $g$ for which $\Phi _l^g$ is smaller than $\Phi _l$, allowing us to handle $l$ over 60000.

References

Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355–380. MR 1023756, DOI 10.1090/S0025-5718-1990-1023756-8
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. MR 2467854, DOI 10.1007/978-3-540-79456-1_{1}9
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
Daniel J. Bernstein and Jonathan P. Sorenson, Modular exponentiation via the explicit Chinese remainder theorem, Math. Comp. 76 (2007), no. 257, 443–454. MR 2261030, DOI 10.1090/S0025-5718-06-01849-7
Ingrid Biehl and Johannes Buchmann, An analysis of the reduction algorithms for binary quadratic forms, Voronoi’s Impact on Modern Science (P. Engel and H. Syta, eds.), Institute of Mathematics, Kyiv, 1998, available at http://www.cdc.informatik.tu-darmstadt. de/reports/TR/TI-97-26.ps.gz, pp. 71–98.
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. MR 2772473, DOI 10.1016/j.jnt.2009.11.003
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. MR 1771549
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.
A. Bostan, F. Morain, B. Salvy, and É. Schost, Fast algorithms for computing isogenies between elliptic curves, Math. Comp. 77 (2008), no. 263, 1755–1778. MR 2398793, DOI 10.1090/S0025-5718-08-02066-8
Reinier Bröker, Constructing elliptic curves of prescribed order, PhD thesis, Universiteit Leiden, 2006.
Reinier Bröker, A $p$-adic algorithm to compute the Hilbert class polynomial, Math. Comp. 77 (2008), no. 264, 2417–2435. MR 2429891, DOI 10.1090/S0025-5718-08-02091-7
—, $p$-adic class invariants, LMS Journal of Computation and Mathematics (2010), to appear.
Reinier Bröker and Andrew V. Sutherland, An explicit height bound for the classical modular polynomial, Ramanujan J. 22 (2010), no. 3, 293–313. MR 2670978, DOI 10.1007/s11139-010-9231-8
Johannes Buchmann and Ulrich Vollmer, Binary quadratic forms, Algorithms and Computation in Mathematics, vol. 20, Springer, Berlin, 2007. An algorithmic approach. MR 2300780
J.J. Cannon and W. Bosma (Eds.), Handbook of Magma functions, 2.15 ed., 2008, available at http://magma.maths.usyd.edu.au/magma/htmlhelp/MAGMA.htm.
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. MR 2538431, DOI 10.1007/978-3-642-01001-9_{1}5
Denis Charles and Kristin Lauter, Computing modular polynomials, LMS J. Comput. Math. 8 (2005), 195–204. MR 2166572, DOI 10.1112/S1461157000000954
Henri Cohen, Advanced topics in computational number theory, Graduate Texts in Mathematics, vol. 193, Springer-Verlag, New York, 2000. MR 1728313, DOI 10.1007/978-1-4419-8489-0
Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren (eds.), Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006. MR 2162716
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. MR 755826, DOI 10.1017/S0305004100061697
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
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. MR 1486831, DOI 10.1090/amsip/007/03
Andreas Enge, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), no. 266, 1089–1107. MR 2476572, DOI 10.1090/S0025-5718-08-02200-X
Andreas Enge, Computing modular polynomials in quasi-linear time, Math. Comp. 78 (2009), no. 267, 1809–1824. MR 2501077, DOI 10.1090/S0025-5718-09-02199-1
Andreas Enge and Francois Morain, Generalized Weber functions I, 2009, http://arxiv.org/ abs/0905.3250.
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). MR 2144957
Andreas Enge and Reinhard Schertz, Modular curves of composite level, Acta Arith. 118 (2005), no. 2, 129–141. MR 2141046, DOI 10.4064/aa118-2-3
Andreas Enge and Andrew V. Sutherland, Class invariants for the CRT method, Algorithmic Number Theory Symposium–ANTS IX (G. Hanrot, F. Morain, and E. Thomé, eds.), Lecture Notes in Computer Science, vol. 6197, Springer-Verlag, 2010, pp. 142–156.
Free Software Foundation, GNU compiler collection, January 2010, version 4.4.3, available at http://gcc.gnu.org/.
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. MR 2041091, DOI 10.1007/3-540-45455-1_{2}3
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. MR 1975526, DOI 10.1007/3-540-46035-7_{3}
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. MR 1726092, DOI 10.1007/BFb0054883
Torbjörn Granlund et al., GNU multiple precision arithmetic library, September 2010, version 5.0.1, available at http://gmplib.org/.
G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, Oxford, at the Clarendon Press, 1954. 3rd ed. MR 67125
David Harvey, $\text {zn\_poly}$: a library for polynomial arithmetic, 2008, version 0.9, http://cims. nyu.edu/~harvey/zn_poly.
David Harvey, Faster polynomial multiplication via multipoint Kronecker substitution, J. Symbolic Comput. 44 (2009), no. 10, 1502–1510. MR 2543433, DOI 10.1016/j.jsc.2009.05.004
Oskar Herrmann, Über die Berechnung der Fourierkoeffizienten der Funktion $j(\tau )$, J. Reine Angew. Math. 274(275) (1975), 187–195 (German). MR 374032, DOI 10.1515/crll.1975.274-275.187
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. MR 2129747, DOI 10.1201/9781420035216
Hideji Ito, Computation of the modular equation, Proc. Japan Acad. Ser. A Math. Sci. 71 (1995), no. 3, 48–50. MR 1332947
M. Jarden, Transfer principles for finite and $p$-adic fields, Nieuw Arch. Wisk. (3) 28 (1980), no. 2, 139–158. MR 582923
Erich Kaltofen and Noriko Yui, On the modular equation of order $11$, Proceedings of the 1984 MACSYMA Users Conference, 1984, pp. 472–485.
David Russell Kohel, Endomorphism rings of elliptic curves over finite fields, ProQuest LLC, Ann Arbor, MI, 1996. Thesis (Ph.D.)–University of California, Berkeley. MR 2695524
J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London-New York, 1977, pp. 409–464. MR 447191
Serge Lang, Elliptic functions, 2nd ed., Graduate Texts in Mathematics, vol. 112, Springer-Verlag, New York, 1987. With an appendix by J. Tate. MR 890960, DOI 10.1007/978-1-4612-4752-4
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. MR 1322712, DOI 10.1007/3-540-58691-1_{4}4
H. W. Lenstra Jr. and Carl Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), no. 3, 483–516. MR 1137100, DOI 10.1090/S0894-0347-1992-1137100-0
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). MR 1413579
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.
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. MR 1697859, DOI 10.1007/978-3-662-03983-0
A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
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). MR 1413578
William Stein and David Joyner, SAGE: System for Algebra and Geometry Experimentation, Communications in Computer Algebra (SIGSAM Bulletin) (2005), 61–64.
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. MR 2467548
Andrew V. Sutherland, Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comp. 80 (2011), no. 273, 501–538. MR 2728992, DOI 10.1090/S0025-5718-2010-02373-7
Jacques Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A238–A241 (French). MR 294345
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
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. MR 2404461, DOI 10.1201/9781420071474
Heinrich Weber, Lehrbuch der algebra, third ed., vol. III, Chelsea, 1961.