Computing Igusa class polynomials

Streng, Marco

doi:10.1090/S0025-5718-2013-02712-3

Computing Igusa class polynomials
HTML articles powered by AMS MathViewer

by Marco Streng PDF

Math. Comp. 83 (2014), 275-309 Request permission

Abstract:

We bound the running time of an algorithm that computes the genus-two class polynomials of a primitive quartic CM-field $K$. This is in fact the first running time bound and even the first proof of correctness of any algorithm that computes these polynomials.

Essential to bounding the running time is our bound on the height of the polynomials, which is a combination of denominator bounds of Goren and Lauter and our own absolute value bounds. The absolute value bounds are obtained by combining Dupont’s estimates of theta constants with an analysis of the shape of CM period lattices (Section 8).

The algorithm is basically the complex analytic method of Spallek and van Wamelen, and we show that it finishes in time $\widetilde {O}(\Delta ^{7/2})$, where $\Delta$ is the discriminant of $K$. We give a complete running time analysis of all parts of the algorithm, and a proof of correctness including a rounding error analysis. We also provide various improvements along the way.

References

Juliana Belding, Reinier Bröker, Andreas Enge, and Kristin Lauter, Computing Hilbert class polynomials, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 5011, Springer, Berlin, 2008, pp. 282–295. MR 2467854, DOI 10.1007/978-3-540-79456-1_{1}9
Daniel J. Bernstein, Fast multiplication and its applications, Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 325–384. MR 2467550
Christina Birkenhake and Herbert Lange, Complex abelian varieties, 2nd ed., Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 302, Springer-Verlag, Berlin, 2004. MR 2062673, DOI 10.1007/978-3-662-06307-1
Oskar Bolza, Darstellung der rationalen ganzen Invarianten der Binärform sechsten Grades durch die Nullwerthe der zugehörigen $\vartheta$-Functionen, Math. Ann. 30 (1887), no. 4, 478–495 (German). MR 1510458, DOI 10.1007/BF01444091
Jan Hendrik Bruinier and Tonghai Yang, CM-values of Hilbert modular functions, Invent. Math. 163 (2006), no. 2, 229–288. MR 2207018, DOI 10.1007/s00222-005-0459-7
J. A. Buchmann and H. W. Lenstra Jr., Approximating rings of integers in number fields, J. Théor. Nombres Bordeaux 6 (1994), no. 2, 221–260 (English, with English and French summaries). MR 1360644
Gabriel Cardona and Jordi Quer, Field of moduli and field of definition for curves of genus 2, Computational aspects of algebraic curves, Lecture Notes Ser. Comput., vol. 13, World Sci. Publ., Hackensack, NJ, 2005, pp. 71–83. MR 2181874, DOI 10.1142/9789812701640_{0}006
Robert Carls, David Kohel, and David Lubicz, Higher-dimensional 3-adic CM construction, J. Algebra 319 (2008), no. 3, 971–1006. MR 2379090, DOI 10.1016/j.jalgebra.2007.11.016
Robert Carls and David Lubicz, A $p$-adic quasi-quadratic time point counting algorithm, Int. Math. Res. Not. IMRN 4 (2009), 698–735. MR 2480098, DOI 10.1093/imrn/rnn143
E. de Shalit and E. Z. Goren, On special values of theta functions of genus two, Ann. Inst. Fourier (Grenoble) 47 (1997), no. 3, 775–799 (English, with English and French summaries). MR 1465786
Régis Dupont. Moyenne arithmético-géométrique, suites de Borchardt et applications. Ph.D. thesis, École Polytechnique, 2006. http://www.lix.polytechnique.fr/Labo/Regis.Dupont/these_soutenance.pdf.
Régis Dupont, Fast evaluation of modular functions using Newton iterations and the AGM, Math. Comp. 80 (2011), no. 275, 1823–1847. MR 2785482, DOI 10.1090/S0025-5718-2011-01880-6
Friedrich Eisenbrand and Günter Rote, Fast reduction of ternary quadratic forms, Cryptography and lattices (Providence, RI, 2001) Lecture Notes in Comput. Sci., vol. 2146, Springer, Berlin, 2001, pp. 32–44. MR 1903885, DOI 10.1007/3-540-44670-2_{4}
Kirsten Eisenträger and Kristin Lauter. A CRT algorithm for constructing genus 2 curves over finite fields. In Arithmetic, Geometry and Coding Theory, AGCT-10 (Marseille, 2005). Société Mathématique de France, 2011.
Andreas Enge, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), no. 266, 1089–1107. MR 2476572, DOI 10.1090/S0025-5718-08-02200-X
Andreas Enge and François Morain. Fast decomposition of polynomials with known Galois group. In Applied algebra, algebraic algorithms and error-correcting codes (Toulouse), LNCS 2643, pages 254–264. Springer, 2003.
Gerhard Frey and Tanja Lange, Complex multiplication, Handbook of elliptic and hyperelliptic curve cryptography, Discrete Math. Appl. (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006, pp. 455–473. MR 2162734
P. Gaudry, T. Houtmann, D. Kohel, C. Ritzenthaler, and A. Weng, The 2-adic CM method for genus 2 curves with application to cryptography, Advances in cryptology—ASIACRYPT 2006, Lecture Notes in Comput. Sci., vol. 4284, Springer, Berlin, 2006, pp. 114–129. MR 2444631, DOI 10.1007/11935230_{8}
Eyal Z. Goren, On certain reduction problems concerning abelian surfaces, Manuscripta Math. 94 (1997), no. 1, 33–43. MR 1468933, DOI 10.1007/BF02677837
Eyal Z. Goren and Kristin E. Lauter, Class invariants for quartic CM fields, Ann. Inst. Fourier (Grenoble) 57 (2007), no. 2, 457–480 (English, with English and French summaries). MR 2310947
Eyal Z. Goren and Kristin Lauter. Genus 2 curves with complex multiplication. Int. Math. Res. Notices, 2012(5):1068–1142, 2012.
Erhard Gottschling, Explizite Bestimmung der Randflächen des Fundamentalbereiches der Modulgruppe zweiten Grades, Math. Ann. 138 (1959), 103–124 (German). MR 107020, DOI 10.1007/BF01342938
Erich Hecke, Vorlesungen über die Theorie der algebraischen Zahlen, Chelsea Publishing Co., Bronx, N.Y., 1970 (German). Second edition of the 1923 original, with an index. MR 0352036
Jun-ichi Igusa, Arithmetic variety of moduli for genus two, Ann. of Math. (2) 72 (1960), 612–649. MR 114819, DOI 10.2307/1970233
Jun-ichi Igusa, On Siegel modular forms of genus two, Amer. J. Math. 84 (1962), 175–200. MR 141643, DOI 10.2307/2372812
Jun-ichi Igusa, Modular forms and projective invariants, Amer. J. Math. 89 (1967), 817–855. MR 229643, DOI 10.2307/2373243
Peter Kirrinnis, Partial fraction decompostion in $\mathbf C(z)$ and simultaneous Newton iteration for factorization in $\mathbf C[z]$, J. Complexity 14 (1998), no. 3, 378–444. MR 1646107, DOI 10.1006/jcom.1998.0481
Helmut Klingen, Introductory lectures on Siegel modular forms, Cambridge Studies in Advanced Mathematics, vol. 20, Cambridge University Press, Cambridge, 1990. MR 1046630, DOI 10.1017/CBO9780511619878
David Kohel et al. ECHIDNA algorithms for algebra and geometry experimentation. http://echidna.maths.usyd.edu.au/~kohel/dbs/complex_multiplication2.html, 2007.
Hendrik W. Lenstra Jr., Lattices, Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 127–181. MR 2467546
Stéphane Louboutin, Explicit lower bounds for residues at $s=1$ of Dedekind zeta functions and relative class numbers of CM-fields, Trans. Amer. Math. Soc. 355 (2003), no. 8, 3079–3098. MR 1974676, DOI 10.1090/S0002-9947-03-03313-0
Jean-François Mestre, Construction de courbes de genre $2$ à partir de leurs modules, Effective methods in algebraic geometry (Castiglioncello, 1990) Progr. Math., vol. 94, Birkhäuser Boston, Boston, MA, 1991, pp. 313–334 (French). MR 1106431
David Mumford, Tata lectures on theta. II, Progress in Mathematics, vol. 43, Birkhäuser Boston, Inc., Boston, MA, 1984. Jacobian theta functions and differential equations; With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman and H. Umemura. MR 742776, DOI 10.1007/978-0-8176-4578-6
René Schoof, Computing Arakelov class groups, Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 447–495. MR 2467554
Goro Shimura and Yutaka Taniyama, Complex multiplication of abelian varieties and its applications to number theory, Publications of the Mathematical Society of Japan, vol. 6, Mathematical Society of Japan, Tokyo, 1961. MR 0125113
Anne-Monika Spallek. Kurven vom Geschlecht $2$ und ihre Anwendung in Public-Key-Kryptosystemen. Ph.D. thesis, Institut für Experimentelle Mathematik, Universität GH Essen, 1994. http://www.iem.uni-due.de/zahlentheorie/AES-KG2.pdf.
William Stein et al. Sage mathematics software 4.7.2, 2011. http://www.sagemath.org/.
Marco Streng. Complex multiplication of abelian surfaces. Ph.D. thesis, Universiteit Leiden, 2010. http://hdl.handle.net/1887/15572.
Carl Johannes Thomae. Beitrag zur Bestimmung von $\vartheta (0,\cdots ,0)$ durch die Klassenmoduln algebraischer Funktionen. J. Reine Angew. Math., 71:201–222, 1870.
Paul van Wamelen, Examples of genus two CM curves defined over the rationals, Math. Comp. 68 (1999), no. 225, 307–320. MR 1609658, DOI 10.1090/S0025-5718-99-01020-0
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
Lawrence C. Washington, Introduction to cyclotomic fields, Graduate Texts in Mathematics, vol. 83, Springer-Verlag, New York, 1982. MR 718674, DOI 10.1007/978-1-4684-0133-2
Heinrich Weber. Algebraische Zahlen, volume 3 of Lehrbuch der Algebra. Friedrich Vieweg, 1908.
Annegret Weng, Constructing hyperelliptic curves of genus 2 suitable for cryptography, Math. Comp. 72 (2003), no. 241, 435–458. MR 1933830, DOI 10.1090/S0025-5718-02-01422-9
Tonghai Yang. Arithmetic intersection on a Hilbert modular surface and the Faltings height. http://www.math.wisc.edu/~thyang/RecentPreprint.html, 2007.