Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2024 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Computing modular polynomials in quasi-linear time
HTML articles powered by AMS MathViewer

by Andreas Enge;
Math. Comp. 78 (2009), 1809-1824
DOI: https://doi.org/10.1090/S0025-5718-09-02199-1
Published electronically: March 11, 2009

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 \[ 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
  • 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
  • Reinier Bröker, Constructing elliptic curves of prescribed order, Proefschrift, Universiteit Leiden, 2006.
  • Denis Charles and Kristin Lauter, Computing modular polynomials, LMS J. Comput. Math. 8 (2005), 195–204. MR 2166572, DOI 10.1112/S1461157000000954
  • 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
  • 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, DOI 10.1007/3-540-45455-1_{1}9
  • M. Deuring, Die Klassenkörper der komplexen Multiplikation, Enzyklopädie der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen, Band I 2, Heft 10, Teil I, B. G. Teubner Verlagsgesellschaft, Stuttgart, 1958 (German). MR 167481
  • 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.
  • 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, 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.
  • —, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), 1089–1107.
  • 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, DOI 10.1007/3-540-45455-1_{2}1
  • —, 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.
  • —, Further investigations of the generalised Weber functions, In preparation, 2007.
  • 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 Paul Zimmermann, mpc — a library for multiprecision complex arithmetic with exact rounding, Version 0.4.6, http://www.multiprecision.org/mpc.
  • 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
  • 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.
  • Steven D. Galbraith, Constructing isogenies between elliptic curves over finite fields, LMS J. Comput. Math. 2 (1999), 118–138. MR 1728955, DOI 10.1112/S1461157000000097
  • Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167
  • Pierrick Gaudry, Assembly support for GMP on AMD64, April 2005, http://www.loria.fr/~gaudry/mpn_AMD64/.
  • Torbjörn Granlund et al., gmp — GNU multiprecision library, Version 4.2.1, http://gmplib.org/.
  • 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.
  • William B. Hart, Evaluation of the Dedekind eta funktion, Ph.D. thesis, Macquarie University, 2004.
  • David Kohel, Endomorphism rings of elliptic curves over finite fields, Ph.D. thesis, University of California at Berkeley, 1996.
  • 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, Dissertation, Universität des Saarlandes, Saarbrücken, 1995.
  • Andrew P. Ogg, Hyperelliptic modular curves, Bull. Soc. Math. France 102 (1974), 449–462. MR 364259
  • L. Schläfli, Beweis der Hermiteschen Verwandlungstafeln für die elliptischen Modulfunktionen, Journal für die reine und angewandte Mathematik 72 (1870), 360–369.
  • 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
  • Jacques Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A238–A241 (French). MR 294345
  • 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
Bibliographic 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
  • Received by editor(s): April 24, 2007
  • Received by editor(s) in revised form: May 13, 2008
  • Published electronically: March 11, 2009
  • © Copyright 2009 Andreas Enge
  • Journal: Math. Comp. 78 (2009), 1809-1824
  • MSC (2000): Primary 11Y16; Secondary 11G15
  • DOI: https://doi.org/10.1090/S0025-5718-09-02199-1
  • MathSciNet review: 2501077