Hostname: page-component-8448b6f56d-cfpbc Total loading time: 0 Render date: 2024-04-16T22:09:11.264Z Has data issue: false hasContentIssue false
  • English
  • Français

A quasi-linear time algorithm for computing modular polynomials in dimension 2

Part of: Computational number theory Discontinuous groups and automorphic forms

Published online by Cambridge University Press:  01 September 2015

Enea Milio
Enea Milio*
Affiliation:
INRIA Bordeaux Sud-Ouest, 33405 Talence, France email enea.milio@inria.fr

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We propose to generalize the work of Régis Dupont for computing modular polynomials in dimension $2$ to new invariants. We describe an algorithm to compute modular polynomials for invariants derived from theta constants and prove heuristically that this algorithm is quasi-linear in its output size. Some properties of the modular polynomials defined from quotients of theta constants are analyzed. We report on experiments with our implementation.

MSC classification

Primary: 11F46: Siegel modular groups; Siegel and Hilbert-Siegel modular and automorphic forms 11Y16: Algorithms; complexity
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 18 , Issue 1 , 2015 , pp. 603 - 632
Copyright
© The Author 2015 

References

Belabas, K. et al. , PARI/GP version 2.5.3, Bordeaux, 2012, http://pari.math.u-bordeaux.fr/.Google Scholar
Belding, J., Bröker, R., Enge, A. and Lauter, K., ‘Computing Hilbert class polynomials’, Algorithmic Number Theory 8th International Symposium (ANTS VIII) , Lecture Notes in Computer Science 5011 (Springer, Berlin, 2008) 282–295.Google Scholar
Birkenhake, C. and Lange, H., Complex abelian varieties , Grundlehren der Mathematischen Wissenschaften 302 (Springer, 2003).Google Scholar
Bisson, G. and Sutherland, A.V., ‘Computing the endomorphism ring of an ordinary elliptic curve over a finite field’, J. Number Theory 113 (2011) 815–831.Google Scholar
Bröker, R. and Lauter, K., ‘Modular polynomials for genus 2’, LMS J. Comput. Math. 12 (2009) no. 1, 326–339.CrossRefGoogle Scholar
Bröker, R., Lauter, K. and Sutherland, A. V., ‘Modular polynomials via isogeny volcanoes’, Math. Comp. 81 (2012) 1201–1231.Google Scholar
Cosset, R., ‘Applications des fonctions thêta à la cryptographie sur courbes hyperelliptiques’, PhD Thesis, Université Henri Poincaré - Nancy 1, 2011.Google Scholar
Davis, P. and Rabinowitz, P., Methods of Numerical Integration , 2nd edn (Academic Press, New York, 1984).Google Scholar
Dupont, R., ‘Moyenne arithmético-géométrique, suites de Borchardt et applications’, PhD Thesis, École polytechnique, 2006, http://www.lix.polytechnique.fr/Labo/Regis.Dupont/.Google Scholar
Eisenträger, K. and Lauter, K., ‘A CRT algorithm for constructing genus 2 curves over finite fields’, Arithmetic, Geometry and Coding Theory (AGCT-10) , Séminaires et Congrès 21 (Société Mathématique de France, Paris, 2009) 161–176.Google Scholar
Elkies, N., ‘Elliptic and modular curves over finite fields and related computational issues’, Computational perspectives on number theory: Proceedings of the conference in honor of A.O.L. Atkin , AMS/IP Studies in Advanced Mathematics 7 (American Mathematical Society, Boston, 1998) 21–76.Google Scholar
Enge, A., ‘Computing modular polynomials in quasi-linear time’, Math. Comp. 78 (2009) 1809–1824, http://hal.inria.fr/hal-00823745.Google Scholar
Enge, A., PARI-GNUMP, version 0.0.1, February 2014, http://www.multiprecision.org/index.php?prog=pari-gnump/.Google Scholar
Enge, A., Gastineau, M., Théveny, P. and Zimmermann, P., GNU MPC - a library for multiprecision complex arithmetic with exact rounding, version 1.0.1, INRIA, September 2012, http://mpc.multiprecision.org/.Google Scholar
Enge, A. and Sutherland, A. V., ‘Class invariants by the CRT method’, Algorithmic Number Theory 9th International Symposium (ANTS IX) , Lecture Notes in Computer Science 6197 (Springer, Berlin, 2010) 142–156.Google Scholar
Enge, A. and Thomé, E., ‘Computing class polynomials for abelian surfaces’, Exp. Math. 23 (2014) 129–145.Google Scholar
Enge, A. and Thomé., E., CMH - computation of Igusa class polynomials, version 1.0, March 2014,http://cmh.gforge.inria.fr/.Google Scholar
Freitag, E., Siegelsche Modulfunktionen , Grundlehren der Mathematischen Wissenschaften 254 (Springer, Berlin, 1983).CrossRefGoogle Scholar
Gottschling, E., ‘Explizite Bestimmung der Randflächen des Fundamentalbereiches der Modulgruppe zweiten Grades’, Ann. of Math. (2) 138 (1959) 103–124.Google Scholar
Granlund, T et al. , GMP - the GNU multiple precision arithmetic library, version 5.1.1, February 2013, http://gmplib.org/.Google Scholar
Gruenewald, D., ‘Explicit algorithms for Humbert surfaces’, PhD Thesis, University of Sydney, 2008.Google Scholar
Hanrot, G., Lefèvre, V., Pélissier, P. and Zimmermann, P. et al. , GNU MPFR - a library for multiple-precision floating-point computations with exact rounding, version 3.1.1, July 2012,http://www.mpfr.org/.Google Scholar
Hirzebruch, F. and Van der Geer, G., Lectures on Hilbert modular surfaces , Séminaire de Mathématiques Supérieures 77 (Presses de l’université de Montréal, Montréal, 1981).Google Scholar
van der Hoeven, J., ‘Fast evaluation of holonomic functions’, Theoret. Comput. Sci. 210 (1999) no. 1, 199–215.Google Scholar
von zur Gathen, J. and Jürgen, G., Modern Computer Algebra (Cambridge University Press, New York, NY, 1999).Google Scholar
Igusa, J. I., ‘Arithmetic variety of moduli for genus 2’, Ann. of Math. (2) 72 (1960) no. 3, 612–649.CrossRefGoogle Scholar
Igusa, J. I., ‘On Siegel modular forms of genus 2’, Amer. J. Math. 84 (1962) 175–200.CrossRefGoogle Scholar
Igusa, J. I., Theta functions , Grundlehren der Mathematischen Wissenschaften 194 (Springer, Berlin, 1972).Google Scholar
Klingen, H., Introductory lectures on Siegel modular forms , Cambridge Studies in Advanced Mathematics 20 (Cambridge University Press, Cambridge, 1990).CrossRefGoogle Scholar
Lang, S., Elliptic functions , Graduate Text in Mathematics 112 (Springer, New York, NY, 1987).CrossRefGoogle Scholar
Manni, R., ‘Modular varieties with level 2 theta structure’, Amer. J. Math. 116 (1994) 1489–1511.Google Scholar
Mestre, J.-F., ‘Construction de courbes de genre 2 à partir de leurs modules’, Effective methods in algebraic geometry , Progress in Mathematics 94 (Birkhäuser, Boston, MA, 1991) 313–334.Google Scholar
Molin, P., ‘Intégration numérique et calculs de fonctions $L$ ’, PhD Thesis, Université Bordeaux 1, 2010.https://github.com/pascalmolin/hcperiods.Google Scholar
Mumford, D., Abelian Varieties , Tata Institute of fundamental research studies in mathematics (Published for the Tata Institute of Fundamental Research, Bombay by Oxford University Press, 1970).Google Scholar
Mumford, D., Tata lectures on theta I , Progress in Mathematics 28 (Birkhäuser, Boston, MA, 1983).Google Scholar
Mumford, D., Tata lectures on theta II , Progress in Mathematics 43 (Birkhäuser, Boston, MA, 1984).Google Scholar
Runge, B., ‘Endomorphism rings of abelian surfaces and projective models of their moduli spaces’, Tohoku Math. J. (2) 51 (1999) no. 3, 283–303.Google Scholar
Schertz, R., Complex multiplication , New Mathematical Monographs 15 (Cambridge University Press, New York, NY, 2010).Google Scholar
Schläfli, L., ‘Beweis der Hermiteschen Verwandlungstafeln für die elliptischen Modulfunktionen’, J. Reine Angew. Math. 72 (1870) 360–369.Google Scholar
Schoof, R., ‘Counting points on elliptic curves over finite fields’, J. Théor. Nombres Bordeaux 7 (1995) 219–264.Google Scholar
Schönhage, A. and Strassen, V., ‘Schnelle Multiplikation grosser Zahlen’, Computing 7 (1971) 281–292.Google Scholar
Streng, M., ‘Complex multiplication of abelian surfaces’, PhD Thesis, Universiteit Leiden, 2010.Google Scholar
Sutherland, A. V., ‘Computing Hilbert class polynomials with the Chinese remainder theorem’, Math. Comp. 80 (2011) 501–538.CrossRefGoogle Scholar
Thomae, J., ‘Beitrag zur Bestimmung von 𝜃(0, 0, …, 0) durch die Klassenmoduln algebraischer Funktionen’, J. Reine Angew. Math. 70 (1870) 201–222.Google Scholar
Weng, A., ‘Constructing hyperelliptic curves of genus 2 suitable for cryptography’, Math. Comp. 72 (2003) no. 241, 435–458.Google Scholar
Zagier, Don, Modular forms of one variable. Notes based on a course given in Utrecht, 1991.http://people.mpim-bonn.mpg.de/zagier/files/tex/UtrechtLectures/UtBook.pdf.Google Scholar