×

zbMATH — the first resource for mathematics

Computing Igusa class polynomials. (English) Zbl 1322.11066
Summary: 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 E. Z. Goren and K. E. Lauter [Ann. Inst. Fourier 57, No. 2, 457–480 (2007; Zbl 1172.11018)] and our own absolute value bounds. The absolute value bounds are obtained by combining Dupont’s estimates of theta constants [R. Dupont, Math. Comput. 80, No. 275, 1823–1847 (2011; Zbl 1221.65075)] with an analysis of the shape of CM period lattices (Section 8). The algorithm is basically the complex analytic method of 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)] and P. van Wamelen [Math. Comput. 68, 307–320 (1999; Zbl 0906.14025)], 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.

MSC:
11G15 Complex multiplication and moduli of abelian varieties
14K22 Complex multiplication and abelian varieties
11Y40 Algebraic number theory computations
Software:
Echidna; SageMath
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] 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. · Zbl 1205.11139 · doi:10.1007/978-3-540-79456-1_19 · doi.org
[2] 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. · Zbl 1208.68239
[3] 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. · Zbl 1056.14063
[4] Oskar Bolza, Darstellung der rationalen ganzen Invarianten der Binärform sechsten Grades durch die Nullwerthe der zugehörigen \?-Functionen, Math. Ann. 30 (1887), no. 4, 478 – 495 (German). · JFM 19.0122.02 · doi:10.1007/BF01444091 · doi.org
[5] Jan Hendrik Bruinier and Tonghai Yang, CM-values of Hilbert modular functions, Invent. Math. 163 (2006), no. 2, 229 – 288. · Zbl 1093.11041 · doi:10.1007/s00222-005-0459-7 · doi.org
[6] 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). · Zbl 0828.11075
[7] 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. · Zbl 1126.14031 · doi:10.1142/9789812701640_0006 · doi.org
[8] Robert Carls, David Kohel, and David Lubicz, Higher-dimensional 3-adic CM construction, J. Algebra 319 (2008), no. 3, 971 – 1006. · Zbl 1140.14042 · doi:10.1016/j.jalgebra.2007.11.016 · doi.org
[9] Robert Carls and David Lubicz, A \?-adic quasi-quadratic time point counting algorithm, Int. Math. Res. Not. IMRN 4 (2009), 698 – 735. · Zbl 1160.11034 · doi:10.1093/imrn/rnn143 · doi.org
[10] 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). · Zbl 0974.11027
[11] 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.
[12] Régis Dupont, Fast evaluation of modular functions using Newton iterations and the AGM, Math. Comp. 80 (2011), no. 275, 1823 – 1847. · Zbl 1221.65075
[13] 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. · Zbl 1006.11080 · doi:10.1007/3-540-44670-2_4 · doi.org
[14] 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. · Zbl 1270.11060
[15] Andreas Enge, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), no. 266, 1089 – 1107. · Zbl 1208.11136
[16] 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. · Zbl 1030.11078
[17] 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.
[18] 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. · Zbl 1172.94576 · doi:10.1007/11935230_8 · doi.org
[19] Eyal Z. Goren, On certain reduction problems concerning abelian surfaces, Manuscripta Math. 94 (1997), no. 1, 33 – 43. · Zbl 0924.14023 · doi:10.1007/BF02677837 · doi.org
[20] 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). · Zbl 1172.11018
[21] Eyal Z. Goren and Kristin Lauter. Genus 2 curves with complex multiplication. Int. Math. Res. Notices, 2012(5):1068-1142, 2012. · Zbl 1236.14033
[22] Erhard Gottschling, Explizite Bestimmung der Randflächen des Fundamentalbereiches der Modulgruppe zweiten Grades, Math. Ann. 138 (1959), 103 – 124 (German). · Zbl 0088.28903 · doi:10.1007/BF01342938 · doi.org
[23] 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. · Zbl 0041.01102
[24] Jun-ichi Igusa, Arithmetic variety of moduli for genus two, Ann. of Math. (2) 72 (1960), 612 – 649. · Zbl 0122.39002 · doi:10.2307/1970233 · doi.org
[25] Jun-ichi Igusa, On Siegel modular forms of genus two, Amer. J. Math. 84 (1962), 175 – 200. · Zbl 0133.33301 · doi:10.2307/2372812 · doi.org
[26] Jun-ichi Igusa, Modular forms and projective invariants, Amer. J. Math. 89 (1967), 817 – 855. · Zbl 0159.50401 · doi:10.2307/2373243 · doi.org
[27] Peter Kirrinnis, Partial fraction decompostion in \?(\?) and simultaneous Newton iteration for factorization in \?[\?], J. Complexity 14 (1998), no. 3, 378 – 444. · Zbl 0934.12005 · doi:10.1006/jcom.1998.0481 · doi.org
[28] Helmut Klingen, Introductory lectures on Siegel modular forms, Cambridge Studies in Advanced Mathematics, vol. 20, Cambridge University Press, Cambridge, 1990. · Zbl 0693.10023
[29] David Kohel et al. ECHIDNA algorithms for algebra and geometry experimentation. http://echidna.maths.usyd.edu.au/ kohel/dbs/complex_multiplication2.html, 2007.
[30] 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. · Zbl 1200.11046
[31] Stéphane Louboutin, Explicit lower bounds for residues at \?=1 of Dedekind zeta functions and relative class numbers of CM-fields, Trans. Amer. Math. Soc. 355 (2003), no. 8, 3079 – 3098. · Zbl 1026.11085
[32] 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). · Zbl 0752.14027
[33] 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. · Zbl 0549.14014
[34] 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. · Zbl 1188.11076
[35] 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, The Mathematical Society of Japan, Tokyo, 1961. · Zbl 0112.03502
[36] 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. · Zbl 0974.11501
[37] William Stein et al. Sage mathematics software 4.7.2, 2011. http://www.sagemath.org/.
[38] Marco Streng. Complex multiplication of abelian surfaces. Ph.D. thesis, Universiteit Leiden, 2010. http://hdl.handle.net/1887/15572. · Zbl 1158.14029
[39] Carl Johannes Thomae. Beitrag zur Bestimmung von \( \vartheta (0,\cdots ,0)\) durch die Klassenmoduln algebraischer Funktionen. J. Reine Angew. Math., 71:201-222, 1870.
[40] Paul van Wamelen, Examples of genus two CM curves defined over the rationals, Math. Comp. 68 (1999), no. 225, 307 – 320. · Zbl 0906.14025
[41] Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. · Zbl 1055.68168
[42] Lawrence C. Washington, Introduction to cyclotomic fields, Graduate Texts in Mathematics, vol. 83, Springer-Verlag, New York, 1982. · Zbl 0484.12001
[43] Heinrich Weber. Algebraische Zahlen, volume 3 of Lehrbuch der Algebra. Friedrich Vieweg, 1908.
[44] Annegret Weng, Constructing hyperelliptic curves of genus 2 suitable for cryptography, Math. Comp. 72 (2003), no. 241, 435 – 458. · Zbl 1013.11023
[45] Tonghai Yang. Arithmetic intersection on a Hilbert modular surface and the Faltings height. http://www.math.wisc.edu/ thyang/RecentPreprint.html, 2007. · Zbl 1298.11056
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.