Computing modular polynomials in quasi-linear time

Enge, Andreas

doi:10.1090/S0025-5718-09-02199-1

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

by Andreas Enge PDF

Math. Comp. 78 (2009), 1809-1824

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 II (Article I 2, vol. 23, B. G. Teubner Verlagsgesellschaft, Stuttgart, 1958 (German). MR 0167481
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.