Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Modular polynomials via isogeny volcanoes


Authors: Reinier Bröker, Kristin Lauter and Andrew V. Sutherland
Journal: Math. Comp. 81 (2012), 1201-1231
MSC (2010): Primary 11Y16; Secondary 11G15, 11G20, 14H52
DOI: https://doi.org/10.1090/S0025-5718-2011-02508-1
Published electronically: July 14, 2011
MathSciNet review: 2869057
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. Eric Bach, Explicit bounds for primality testing and related problems, Mathematics of Computation 55 (1990), no. 191, 355-380. MR 1023756 (91m:11096)
  • 2. Juliana Belding, Reinier Bröker, Andreas Enge, and Kristin Lauter, Computing Hilbert class polynomials, Algorithmic Number Theory Symposium-ANTS VIII (A. J. van der Poorten and A. Stein, eds.), Lecture Notes in Computer Science, vol. 5011, Springer, 2008, pp. 282-295. MR 2467854 (2009j:11200)
  • 3. Elwyn R. Berlekamp, Factoring polynomials over large finite fields, Mathematics of Computation 24 (1970), no. 111, 713-735. MR 0276200 (43:1948)
  • 4. Daniel J. Bernstein, Modular exponentiation via the explicit Chinese Remainder Theorem, Mathematics of Computation 76 (2007), 443-454. MR 2261030 (2007f:11142)
  • 5. 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.
  • 6. Gaetan Bisson and Andrew V. Sutherland, Computing the endomorphism ring of an ordinary elliptic curve over a finite field, Journal of Number Theory 113 (2011), pp. 815-831. MR 2772473
  • 7. Ian Blake, Gadiel Seroussi, and Nigel Smart, Elliptic curves in cryptography, London Mathematical Society Lecture Note Series, vol. 265, Cambridge University Press, 1999. MR 1771549 (2001i:94048)
  • 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. Alin Bostan, Bruno Salvy, François Morain, and Éric Schost, Fast algorithms for computing isogenies between elliptic curves, Mathematics of Computation 77 (2008), 1755-1778. MR 2398793 (2009k:11207)
  • 10. Reinier Bröker, Constructing elliptic curves of prescribed order, PhD thesis, Universiteit Leiden, 2006.
  • 11. -, A $ p$-adic algorithm to compute the Hilbert class polynomial, Mathematics of Computation 77 (2008), 2417-2435. MR 2429891 (2009j:11093)
  • 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 Journal 22 (2010), 293-313. MR 2670978
  • 14. Johannes Buchmann and Ulrich Vollmer, Binary quadratic forms: an algorithmic approach, Algorithms and Computations in Mathematics, vol. 20, Springer, 2007. MR 2300780 (2008b:11046)
  • 15. 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.
  • 16. Guilhem Castagnos and Fabien Laguillaumie, On the security of cryptosystems with quadratic decryption: the nicest cryptanalysis, Advances in Cryptology: EUROCRYPT 2009 (A. Joux, ed.), Lecture Notes in Computer Science, vol. 5479, Springer, 2009, pp. 260-277. MR 2538431
  • 17. Denis Charles and Kristin Lauter, Computing modular polynomials, LMS Journal of Computation and Mathematics 8 (2005), 195-204. MR 2166572 (2007a:11080)
  • 18. Henri Cohen, Advanced topics in computational number theory, Springer, 2000. MR 1728313 (2000k:11144)
  • 19. Henri Cohen and Gerhard Frey et al., Handbook of elliptic and hyperelliptic curve cryptography, Chapman and Hall, 2006. MR 2162716 (2007f:14020)
  • 20. Paula Cohen, On the coefficients of the transformation polynomials for the elliptic modular function, Math. Proc. of the Cambridge Philosophical Society 95 (1984), 389-402. MR 755826 (85k:11020)
  • 21. David A. Cox, Primes of the form $ x^2+ny^2$: Fermat, class field theory, and complex multiplication, John Wiley and Sons, 1989. MR 1028322 (90m:11016)
  • 22. Noam D. Elkies, Elliptic and modular curves over finite fields and related computational issues, Computational Perspectives on Number Theory (D. A. Buell and J. T. Teitelbaum, eds.), Studies in Advanced Mathematics, vol. 7, AMS, 1998, pp. 21-76. MR 1486831 (99a:11078)
  • 23. Andreas Enge, The complexity of class polynomial computation via floating point approximations, Mathematics of Computation 78 (2009), 1089-1107. MR 2476572 (2010h:11097)
  • 24. -, Computing modular polynomials in quasi-linear time, Mathematics of Computation 78 (2009), 1809-1824. MR 2501077 (2010b:11171)
  • 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, Journal de Théorie des Nombres de Bordeaux 16 (2004), no. 3, 555-568. MR 2144957 (2006d:11063)
  • 27. -, Modular curves of composite level, Acta Arithmetica 118 (2005), no. 2, 129-141. MR 2141046 (2006a:11074)
  • 28. 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.
  • 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 Symposium-ANTS V (C. Fieker and D. R. Kohel, eds.), Lecture Notes in Computer Science, vol. 2369, Springer, 2002, pp. 276-291. MR 2041091 (2005c:11077)
  • 31. Steven D. Galbraith, Florian Hess, and Nigel P. Smart, Extending the GHS Weil descent attack, Advances in Cryptology--EUROCRYPT 2002, Lecture Notes in Computer Science, vol. 2332, Springer, 2002, pp. 29-44. MR 1975526 (2004f:94060)
  • 32. Alice Gee and Peter Stevenhagen, Generating class fields with Shimura reciprocity, Algorithmic Number Theory Symposium-ANTS III, Lecture Notes in Computer Science, vol. 1423, Springer, 1998, pp. 442-453. MR 1726092 (2000m:11112)
  • 33. Torbjörn Granlund et al., GNU multiple precision arithmetic library, September 2010, version 5.0.1, available at http://gmplib.org/.
  • 34. Godfrey H. Hardy and Edward M. Wright, An introduction to the theory of numbers, fifth ed., Oxford Science Publications, 1979. MR 0067125 (16:673c)
  • 35. David Harvey, $\text{zn\_poly}$: a library for polynomial arithmetic, 2008, version 0.9, http://cims. nyu.edu/~harvey/zn_poly.
  • 36. -, Faster polynomial multiplication via multipoint Kronecker substitution, Journal of Symbolic Computation 44 (2009), no. 10, 1502-1510. MR 2543433 (2010j:13052)
  • 37. Oskar Herrmann, Uber die Berechnung der Fourierkoeffizienten der Funktion $ j(\tau)$, J. Reine Agnew. Math. 274/275 (1975), 187-195. MR 0374032 (51:10232)
  • 38. Derek F. Holt, Bettina Eick, and Eamonn A. O'Brien, Handbook of computational group theory, CRC Press, 2005. MR 2129747 (2006f:20001)
  • 39. Hideji Ito, Computation of the modular equation, Proc. Japan Acad. Ser. A 71 (1995), 48-50. MR 1332947 (96c:11043)
  • 40. Moshe Jarden, Transfer principles for finite and p-adic fields, Nieuw Archief voor Wiskunde 3 (1980), no. 28, 139-158, MR 582923 (83h:12041)
  • 41. Erich Kaltofen and Noriko Yui, On the modular equation of order $ 11$, Proceedings of the 1984 MACSYMA Users Conference, 1984, pp. 472-485.
  • 42. David Kohel, Endomorphism rings of elliptic curves over finite fields, PhD thesis, University of California at Berkeley, 1996. MR 2695524
  • 43. 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, Duram, 1975), Academic Press, 1977, pp. 409-464. MR 0447191 (56:5506)
  • 44. Serge Lang, Elliptic functions, second ed., Springer-Verlag, 1987. MR 890960 (88c:11028)
  • 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 Symposium-ANTS I (L. M. Adleman and M.-D. Huang, eds.), Lecture Notes in Computer Science, vol. 877, 1994, pp. 60-70. MR 1322712 (95m:11148)
  • 46. Hendrik W. Lenstra, Jr. and Carl Pomerance, A rigorous time bound for factoring integers, Journal of the American Mathematical Society 5 (1992), no. 3, 483-516. MR 1137100 (92m:11145)
  • 47. François Morain, Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques, Journal de Théorie des Nombres de Bordeaux 7 (1995), no. 1, 111-138. MR 1413579 (97i:11069)
  • 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, Springer, 1999. MR 1697859 (2000m:11104)
  • 50. Arnold Schönhage and Volker Strassen, Schnelle Multiplikation großer Zahlen, Computing 7 (1971), 281-292. MR 0292344 (45:1431)
  • 51. René Schoof, Counting points on elliptic curves over finite fields, Journal de Théorie des Nombres de Bordeaux 7 (1995), 219-254. MR 1413578 (97i:11070)
  • 52. William Stein and David Joyner, SAGE: System for Algebra and Geometry Experimentation, Communications in Computer Algebra (SIGSAM Bulletin) (2005), 61-64.
  • 53. Peter Stevenhagen, The arithmetic of number rings, Algorithmic Number Theory: Lattices, Number Fields, and Cryptography (J.P. Buhler and P. Stevenhagen, eds.), Mathematical Sciences Research Institute Publications, vol. 44, Cambridge University Press, 2008. MR 2467548 (2009k:11213)
  • 54. Andrew V. Sutherland, Computing Hilbert class polynomials with the Chinese Remainder Theorem, Mathematics of Computation 80 (2011), 501-538. MR 2728992
  • 55. Jacques Vélu, Isogénies entre courbes elliptiques, Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, Séries A et B 273 (1971), 238-241. MR 0294345 (45:3414)
  • 56. Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, second ed., Cambridge University Press, 2003. MR 2001757 (2004g:68202)
  • 57. Lawrence C. Washington, Elliptic curves: Number theory and cryptography, second ed., CRC Press, 2008. MR 2404461 (2009b:11101)
  • 58. Heinrich Weber, Lehrbuch der algebra, third ed., vol. III, Chelsea, 1961.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 11G15, 11G20, 14H52

Retrieve articles in all journals with MSC (2010): 11Y16, 11G15, 11G20, 14H52


Additional Information

Reinier Bröker
Affiliation: Brown University, Box 1917, 151 Thayer Street, Providence, Rhode Island 02192
Email: reinier@math.brown.edu

Kristin Lauter
Affiliation: Microsoft Research, One Microsoft Way, Redmond, Washington 98052
Email: klauter@microsoft.com

Andrew V. Sutherland
Affiliation: Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: drew@math.mit.edu

DOI: https://doi.org/10.1090/S0025-5718-2011-02508-1
Received by editor(s): January 12, 2010
Received by editor(s) in revised form: November 21, 2010
Published electronically: July 14, 2011
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society