Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

   
 

 

Computing modular polynomials in quasi-linear time


Author: Andreas Enge
Journal: Math. Comp. 78 (2009), 1809-1824
MSC (2000): Primary 11Y16; Secondary 11G15
Published electronically: March 11, 2009
MathSciNet review: 2501077
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We analyse and compare the complexity of several algorithms for computing modular polynomials. Under the assumption that rounding errors do not influence the correctness of the result, which appears to be satisfied in practice, we show that an algorithm relying on floating point evaluation of modular functions and on interpolation has a complexity that is up to logarithmic factors linear in the size of the computed polynomials. In particular, it obtains the classical modular polynomial $ \Phi_\ell$ of prime level $ \ell$ in time

$\displaystyle O \left(\ell^2 \log^3 \ell M (\ell) \right) \subseteq O \left( \ell^3 \log^{4 + \varepsilon}\ell\right), $

where $ M(\ell)$ is the time needed to multiply two $ \ell$-bit numbers.

Besides treating modular polynomials for $ \Gamma^0 (\ell)$, which are an important ingredient in many algorithms dealing with isogenies of elliptic curves, the algorithm is easily adapted to more general situations. Composite levels are handled just as easily as prime levels, as well as polynomials between a modular function and its transform of prime level, such as the Schläfli polynomials and their generalisations.

Our distributed implementation of the algorithm confirms the theoretical analysis by computing modular equations of record level around $ 10000$ in less than two weeks on ten processors.


References [Enhancements On Off] (What's this?)

  • 1. Jonathan M. Borwein and Peter B. Borwein, Pi and the AGM, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1987. A study in analytic number theory and computational complexity; A Wiley-Interscience Publication. MR 877728
  • 2. Reinier Bröker, Constructing elliptic curves of prescribed order, Proefschrift, Universiteit Leiden, 2006.
  • 3. Denis Charles and Kristin Lauter, Computing modular polynomials, LMS J. Comput. Math. 8 (2005), 195–204. MR 2166572, 10.1112/S1461157000000954
  • 4. 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, 10.1017/S0305004100061697
  • 5. Jean-Marc Couveignes and Thierry Henocq, Action of modular correspondences around CM points, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 234–243. MR 2041087, 10.1007/3-540-45455-1_19
  • 6. 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
  • 7. Régis Dupont, Fast evaluation of modular functions using Newton iterations and the AGM, To appear in Mathematics of Computation, http://www.lix.polytechnique.fr/Labo/Regis.Dupont/preprints/Dupont_FastEvalMod.ps.gz, 2007.
  • 8. 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
  • 9. Andreas Enge, mpfrcx -- a library for univariate polynomials over arbitrary precision real or complex numbers, Version 0.1, http://www.lix.polytechnique.fr/Labo/Andreas.Enge/Software.html.
  • 10. -, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), 1089-1107.
  • 11. Andreas Enge and François Morain, Comparing invariants for class fields of imaginary quadratric fields, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 252–266. MR 2041089, 10.1007/3-540-45455-1_21
  • 12. -, SEA in genus 1: 2500 decimal digits, December 2006, Posting to the Number Theory List, http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0612&L=NMBRTHRY&P=R125&I =-3.
  • 13. -, Further investigations of the generalised Weber functions, In preparation, 2007.
  • 14. 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
  • 15. Andreas Enge and Reinhard Schertz, Modular curves of composite level, Acta Arith. 118 (2005), no. 2, 129–141. MR 2141046, 10.4064/aa118-2-3
  • 16. Andreas Enge and Paul Zimmermann, mpc -- a library for multiprecision complex arithmetic with exact rounding, Version 0.4.6, http://www.multiprecision.org/mpc.
  • 17. 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, 10.1007/3-540-45455-1_23
  • 18. Martin Fürer, Faster integer multiplication, Proceedings of the 39th Annual ACM Symposium on Theory of Computing -- STOC'07 (New York) (Association for Computing Machinery, ed.), ACM, 2007, pp. 57-66.
  • 19. Steven D. Galbraith, Constructing isogenies between elliptic curves over finite fields, LMS J. Comput. Math. 2 (1999), 118–138 (electronic). MR 1728955, 10.1112/S1461157000000097
  • 20. Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167
  • 21. Pierrick Gaudry, Assembly support for GMP on AMD64, April 2005, http://www.loria.fr/~gaudry/mpn_AMD64/.
  • 22. Torbjörn Granlund et al., gmp -- GNU multiprecision library, Version 4.2.1, http://gmplib.org/.
  • 23. Guillaume Hanrot, Vincent Lefèvre, Patrick Pélissier, and Paul Zimmermann et al., mpfr -- a library for multiple-precision floating-point computations with exact rounding, Version 2.2.1, http://www.mpfr.org.
  • 24. William B. Hart, Evaluation of the Dedekind eta funktion, Ph.D. thesis, Macquarie University, 2004.
  • 25. David Kohel, Endomorphism rings of elliptic curves over finite fields, Ph.D. thesis, University of California at Berkeley, 1996.
  • 26. 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
  • 27. Volker Müller, Ein Algorithmus zur Bestimmung der Punktanzahl elliptischer Kurven über endlichen Körpern der Charakteristik größer drei, Dissertation, Universität des Saarlandes, Saarbrücken, 1995.
  • 28. Andrew P. Ogg, Hyperelliptic modular curves, Bull. Soc. Math. France 102 (1974), 449–462. MR 0364259
  • 29. L. Schläfli, Beweis der Hermiteschen Verwandlungstafeln für die elliptischen Modulfunktionen, Journal für die reine und angewandte Mathematik 72 (1870), 360-369.
  • 30. A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 0292344
  • 31. Jacques Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A238–A241 (French). MR 0294345
  • 32. Heinrich Weber, Lehrbuch der Algebra, 2nd ed., vol. 3: Elliptische Funktionen und algebraische Zahlen, Vieweg, Braunschweig, 1908.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 11G15

Retrieve articles in all journals with MSC (2000): 11Y16, 11G15


Additional Information

Andreas Enge
Affiliation: INRIA Saclay–Île-de-France & Laboratoire d’Informatique (CNRS/UMR 7161), École polytechnique, 91128 Palaiseau Cedex, France
Email: enge@lix.polytechnique.fr

DOI: https://doi.org/10.1090/S0025-5718-09-02199-1
Received by editor(s): April 24, 2007
Received by editor(s) in revised form: May 13, 2008
Published electronically: March 11, 2009
Article copyright: © Copyright 2009 Andreas Enge