×

Computing modular polynomials in quasi-linear time. (English) Zbl 1215.11121

The paper under review deals with the problem of computation of modular polynomials. After surveying the present state of art, the author presents an interesting algorithm based on evaluation and interpolation that computes modular polynomials having a complexity that is up to logarithmic factors linear in the bit size of the computed polynomials. As it is based on floating point computations, it is assumed that rounding errors do not influence the correctness of the output which appears to be satisfied in practice. In particular, it computes the classical modular polynomial \(\Phi_{\ell}\) of prime level \(\ell\) in time \(O(\ell^2 \log^3\ell \;M(\ell))\), where \(M(\ell)\) is the time needed to multiply two \(\ell\)-bit numbers.

MSC:

11Y16 Number-theoretic algorithms; complexity
11G15 Complex multiplication and moduli of abelian varieties
11G50 Heights

Software:

MPC; gmp; MPFR
PDFBibTeX XMLCite
Full Text: DOI

References:

[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. · Zbl 0611.10001
[2] Reinier Bröker, Constructing elliptic curves of prescribed order, Proefschrift, Universiteit Leiden, 2006. · Zbl 1162.11028
[3] Denis Charles and Kristin Lauter, Computing modular polynomials, LMS J. Comput. Math. 8 (2005), 195 – 204. · Zbl 1119.11030 · doi: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. · Zbl 0541.10026 · doi: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. · Zbl 1057.11026 · doi: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). · Zbl 0123.04001
[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. · Zbl 1221.65075
[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. · Zbl 0915.11036
[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. · Zbl 1208.11136
[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. · Zbl 1058.11077 · doi: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). · Zbl 1072.11039
[15] Andreas Enge and Reinhard Schertz, Modular curves of composite level, Acta Arith. 118 (2005), no. 2, 129 – 141. · Zbl 1158.11322 · doi: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. · Zbl 1058.11041 · doi: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) , ACM, 2007, pp. 57-66. · Zbl 1179.68198
[19] Steven D. Galbraith, Constructing isogenies between elliptic curves over finite fields, LMS J. Comput. Math. 2 (1999), 118 – 138. · Zbl 1018.11028 · doi:10.1112/S1461157000000097
[20] Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. · Zbl 0936.11069
[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. · Zbl 1365.65302
[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). · Zbl 0843.11030
[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. · Zbl 0314.10018
[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. · JFM 02.0238.02
[30] A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281 – 292 (German, with English summary). · Zbl 0223.68007
[31] Jacques Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A238 – A241 (French). · Zbl 0225.14014
[32] Heinrich Weber, Lehrbuch der Algebra, 2nd ed., vol. 3: Elliptische Funktionen und algebraische Zahlen, Vieweg, Braunschweig, 1908.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.