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, Wiley, New York, 1987. MR 877728 (89a:11134)
  • 2. Reinier Bröker, Constructing elliptic curves of prescribed order, Proefschrift, Universiteit Leiden, 2006.
  • 3. Denis Charles and Kristin Lauter, Computing modular polynomials, LMS Journal of Computation and Mathematics 8 (2005), 195-204. MR 2166572 (2007a:11080)
  • 4. Paula Cohen, On the coefficients of the transformation polynomials for the elliptic modular function, Mathematical Proceedings of the Cambridge Philosophical Society 95 (1984), 389-402. MR 755826 (85k:11020)
  • 5. Jean-Marc Couveignes and Thierry Henocq, Action of modular correspondences around CM points, Algorithmic Number Theory -- ANTS-V (Berlin) (Claus Fieker and David R. Kohel, eds.), Lecture Notes in Computer Science, vol. 2369, Springer-Verlag, 2002, pp. 234-243. MR 2041087 (2005b:11077)
  • 6. Max Deuring, Die Klassenkörper der komplexen Multiplikation, Enzyklop. d. math. Wissenschaften, vol. I 2 Heft 10, Teubner, Stuttgart, 2e ed., 1958. MR 0167481 (29:4754)
  • 7. Régis Dupont, Fast evaluation of modular functions using Newton iterations and the AGM, To appear in Mathematics of Computation,, 2007.
  • 8. Noam D. Elkies, Elliptic and modular curves over finite fields and related computational issues, Computational Perspectives on Number Theory: Proceedings of a Conference in Honor of A.O.L. Atkin (D. A. Buell and J. T. Teitelbaum, eds.), Studies in Advanced Mathematics, vol. 7, American Mathematical Society, 1998, pp. 21-76. MR 1486831 (99a:11078)
  • 9. Andreas Enge, mpfrcx -- a library for univariate polynomials over arbitrary precision real or complex numbers, Version 0.1,
  • 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 quadratic fields, Algorithmic Number Theory -- ANTS-V (Berlin) (Claus Fieker and David R. Kohel, eds.), Lecture Notes in Computer Science, vol. 2369, Springer-Verlag, 2002, pp. 252-266. MR 2041089 (2005a:11179)
  • 12. -, SEA in genus 1: 2500 decimal digits, December 2006, Posting to the Number Theory List, =-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, Journal de Théorie des Nombres de Bordeaux 16 (2004), 555-568. MR 2144957 (2006d:11063)
  • 15. -, Modular curves of composite level, Acta Arithmetica 118 (2005), no. 2, 129-141. MR 2141046 (2006a:11074)
  • 16. Andreas Enge and Paul Zimmermann, mpc -- a library for multiprecision complex arithmetic with exact rounding, Version 0.4.6,
  • 17. Mireille Fouquet and François Morain, Isogeny volcanoes and the SEA algorithm, Algorithmic Number Theory -- ANTS-V (Berlin) (Claus Fieker and David R. Kohel, eds.), Lecture Notes in Computer Science, vol. 2369, Springer-Verlag, 2002, pp. 276-291. MR 2041091 (2005c:11077)
  • 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 Journal of Computation and Mathematics 2 (1999), no. 2, 118-138. MR 1728955 (2001k:11113)
  • 20. Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, 1999. MR 1689167 (2000j:68205)
  • 21. Pierrick Gaudry, Assembly support for GMP on AMD64, April 2005,
  • 22. Torbjörn Granlund et al., gmp -- GNU multiprecision library, Version 4.2.1,
  • 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,
  • 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, Journal de Théorie des Nombres de Bordeaux 7 (1995), no. 1, 111-138. MR 1413579 (97i:11069)
  • 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, Bulletin de la Société Mathématique de France 102 (1974), 449-462. MR 0364259 (51:514)
  • 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 großer Zahlen, Computing 7 (1971), 281-292. MR 0292344 (45:1431)
  • 31. Jacques Vélu, Isogénies entre courbes elliptiques, Comptes Rendus de l'Académie des Sciences de Paris, Série A 273 (1971), 238-241. MR 0294345 (45:3414)
  • 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

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

American Mathematical Society