×

Modular polynomials on Hilbert surfaces. (English) Zbl 1456.11078

Summary: We describe an evaluation/interpolation approach to compute modular polynomials on a Hilbert surface, which parametrizes abelian surfaces with maximal real multiplication. Under some heuristics we obtain a quasi-linear algorithm. The corresponding modular polynomials are much smaller than the ones on the Siegel threefold. We explain how to compute even smaller polynomials by using pullbacks of theta functions to the Hilbert surface.

MSC:

11F41 Automorphic forms on \(\mbox{GL}(2)\); Hilbert and Hilbert-Siegel modular groups and their modular and automorphic forms; Hilbert modular surfaces
11G18 Arithmetic aspects of modular and Shimura varieties
11Y40 Algebraic number theory computations
14G35 Modular and Shimura varieties
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Baily, W. L.; Borel, A., Compactification of arithmetic quotients of bounded symmetric domains, Ann. Math., 84, 3, 442-528 (1966) · Zbl 0154.08602
[2] Becker, T., On Gröbner bases under specialization, Appl. Algebra Eng. Commun. Comput., 5, 1, 1-8 (1994) · Zbl 0797.13015
[3] Birkenhake, C.; Lange, H., Complex Abelian Varieties, Grundlehren der Mathematischen Wissenschaften., vol. 302 (2003), Springer
[4] Birkenhake, C.; Wilhelm, H., Humbert surfaces and the Kummer plane, Trans. Am. Math. Soc., 355, 5, 1819-1841 (2003) · Zbl 1059.14056
[5] Bröker, R.; Lauter, K., Modular polynomials for genus 2, LMS J. Comput. Math., 12, 326-339 (Jan. 2009) · Zbl 1252.11051
[6] Bröker, R.; Gruenewald, D.; Lauter, K., Explicit CM theory for level 2-structures on Abelian surfaces, Algebra Number Theory, 5, 4, 495-528 (2011) · Zbl 1254.11060
[7] Bröker, R.; Lauter, K.; Sutherland, A., Modular polynomials via isogeny volcanoes, Math. Comput., 81, 278, 1201-1231 (2012) · Zbl 1267.11125
[8] Brooks, E. H.; Jetchev, D.; Wesolowski, B., Isogeny graphs of ordinary Abelian varieties, Res. Number Theory, 3, 1 (2017) · Zbl 1411.11049
[9] Bruinier, J. H., Hilbert modular forms and their applications, (The 1-2-3 of Modular Forms (2008), Springer), 105-179 · Zbl 1259.11050
[10] Charles, D.; Lauter, K.; Goren, E., Cryptographic hash functions from expander graphs, J. Cryptol., 22, 1, 93-113 (2009) · Zbl 1166.94006
[11] Couveignes, J.; Lercier, R., Elliptic periods for finite fields, Finite Fields Appl., 15, 1, 1-22 (2009) · Zbl 1216.11106
[12] De Feo, L.; Jao, D.; Plût, J., Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, J. Math. Cryptol., 8, 3, 209-247 (2014) · Zbl 1372.94419
[13] Doche, C.; Icart, T.; Kohel, D., Efficient scalar multiplication by isogeny decompositions, (Public Key Cryptography-PKC 2006 (2006)), 191-206 · Zbl 1151.94506
[14] Dudeanu, A., Computational Aspects of Jacobians of Hyperelliptic Curves (2016), École Polytechnique Fédérale de Lausanne, PhD thesis
[15] A. Dudeanu, D. Jetchev, D. Robert, M. Vuille, Cyclic Isogenies for Abelian Varieties with Real Multiplication. · Zbl 1498.11147
[16] Dupont, R., Moyenne arithmético-géométrique, suites de Borchardt et applications (2006), École Polytechnique, PhD thesis
[17] Dupont, R., Fast evaluation of modular functions using Newton iterations and the AGM, Math. Comput., 80, 275, 1823-1847 (2011) · Zbl 1221.65075
[18] 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. Computational Perspectives on Number Theory: Proceedings of the Conference in Honor of A.O.L. Atkin, AMS/IP Studies in Advanced Mathematics, vol. 7 (1998), AMS), 21-76 · Zbl 0915.11036
[19] Elkies, N.; Kumar, A., K3 surfaces and equations for Hilbert modular surfaces, Algebra Number Theory, 8, 10, 2297-2411 (2014) · Zbl 1317.11048
[20] Enge, A., Computing modular polynomials in quasi-linear time, Math. Comput., 78, 267, 1809-1824 (2009) · Zbl 1215.11121
[21] Enge, A.; Sutherland, A., Class invariants by the CRT method, (ANTS IX: Proceedings of the Algorithmic Number Theory 9th International Symposium. ANTS IX: Proceedings of the Algorithmic Number Theory 9th International Symposium, Lecture Notes in Computer Science, vol. 6197 (July 2010)), 142-156 · Zbl 1260.11083
[22] Enge, A.; Thomé, E., Computing class polynomials for Abelian surfaces, Exp. Math., 23, 2, 129-145 (2014) · Zbl 1293.11107
[23] Enge, A.; Morain, F., Comparing invariants for class fields of imaginary quadratic fields, (Algorithmic Number Theory (2002), Springer), 252-266 · Zbl 1058.11077
[24] Freitag, E., Hilbert modular forms, (Hilbert Modular Forms (1990), Springer), 5-71 · Zbl 0702.11029
[25] Galbraith, S.; Hess, F.; Smart, N., Extending the GHS Weil descent attack, (Advances in Cryptology—EUROCRYPT 2002 (2002), Springer), 29-44 · Zbl 1055.94013
[26] von zur Gathen, J.; Jürgen, G., Modern Computer Algebra (1999), Cambridge University Press: Cambridge University Press New York, NY, USA · Zbl 0936.11069
[27] Gaudry, P., Algorithmique des courbes hyperelliptiques et applications à la cryptologie (2000), École Polytechnique, PhD thesis
[28] Gaudry, P., Fast genus 2 arithmetic based on theta functions, J. Math. Cryptol., 1, 3, 243-265 (2007) · Zbl 1145.11048
[29] Gaudry, P.; Houtmann, T.; Kohel, D.; Ritzenthaler, C.; Weng, A., The 2-adic CM method for genus 2 curves with application to cryptography, (International Conference on the Theory and Application of Cryptology and Information Security (2006), Springer), 114-129 · Zbl 1172.94576
[30] van der Geer, G., On the geometry of a Siegel modular threefold, Math. Ann., 260, 3, 317-350 (1982) · Zbl 0473.14017
[31] van der Geer, G., Hilbert Modular Surfaces, vol. 16 (2012), Springer Science & Business Media
[32] Goren, E. Z., Lectures on Hilbert Modular Varieties and Modular Forms (2002), American Mathematical Soc. · Zbl 0986.11037
[33] Gruenewald, D., Explicit algorithms for Humbert surfaces (2008), University of Sydney, PhD thesis
[34] Gundlach, K.-B., Die Bestimmung der Funktionen zur Hilbertschen Modulgruppe des Zahlkörpers \(\mathbb{Q}(\sqrt{ 5})\), Math. Ann., 152, 226-256 (1963) · Zbl 0168.06204
[35] Gundlach, K.-B., Die Bestimmung der Funktionen zu einigen Hilbertschen Modulgruppen, J. Reine Angew. Math., 220 (1965) · Zbl 0166.34002
[36] Hirzebruch, F.; Zagier, D., Classification of Hilbert modular surfaces, (Baily, W. L.J.; Shioda, T., Complex Analysis and Algebraic Geometry (1977), Cambridge University Press), 43-78 · Zbl 0354.14011
[37] Humbert, G., Sur les fonctions abéliennes singulières I, J. Math. Pures Appl., serie 5 V, 233-350 (1899) · JFM 30.0408.04
[38] Humbert, G., Sur les fonctions abéliennes singulières II, J. Math. Pures Appl., serie 5 VI, 279-386 (1900) · JFM 31.0455.04
[39] Humbert, G., Sur les fonctions abéliennes singulières III, J. Math. Pures Appl., serie 5 VII, 97-124 (1901) · JFM 32.0456.02
[40] Igusa, J., Arithmetic variety of moduli for genus 2, Ann. Math., 72, 3 (1960) · Zbl 0122.39002
[41] Igusa, J., On Siegel modular forms of genus 2, Am. J. Math., 84, 1 (1962)
[42] Igusa, J., Modular forms and projective invariants, Am. J. Math., 89, 3 (1967) · Zbl 0159.50401
[43] Kalkbrener, M., On the stability of Gröbner bases under specializations, J. Symb. Comput., 24, 1, 51-58 (1997) · Zbl 1054.13502
[44] King, O., The subgroup structure of finite classical groups in terms of geometric configurations, (Webb, B. S., Surveys in Combinatorics 2005 (2005), Cambridge University Press), 29-56 · Zbl 1107.20035
[45] Labrande, H., Explicit computation of the Abel-Jacobi map and its inverse (2016), Université de Lorraine, PhD thesis
[46] Labrande, H., Computing Jacobi’s theta in quasi-linear time, Math. Comput., 87, 1479-1508 (2018) · Zbl 1430.11167
[47] Labrande, H.; Thomé, E., Computing theta functions in quasi-linear time in genus two and above, LMS J. Comput. Math., 19, A, 163-177 (2016) · Zbl 1361.14028
[48] Lauter, K.; Naehrig, M.; Yang, T., Hilbert theta series and invariants of genus 2 curves, J. Number Theory (2015)
[49] Lauter, K.; Yang, T., Computing genus 2 curves from invariants on the Hilbert moduli space, J. Number Theory, Elliptic Curve Cryptogr., 131, 5 (2011) · Zbl 1225.11084
[50] Lauter, K. E.; Robert, D., Improved CRT algorithm for class polynomials in genus 2, (ANTS X — Proceedings of the Tenth Algorithmic Number Theory Symposium. ANTS X — Proceedings of the Tenth Algorithmic Number Theory Symposium, The Open Book Series, vol. 1 (2013), Mathematical Sciences Publisher), 437-461 · Zbl 1344.11046
[51] Lenstra, A. K.; Lenstra, H. W.; Lovász, L., Factoring polynomials with rational coefficients, Math. Ann., 261, 4, 515-534 (1982) · Zbl 0488.12001
[52] Manni, R., Modular varieties with level 2 theta structure, Am. J. Math., 116, 1489-1511 (1994) · Zbl 0818.11023
[53] Martindale, C., Isogeny Graphs, Modular Polynomials, and Applications (2018), Universiteit Leiden, PhD thesis
[54] Martindale, C., Hilbert modular polynomials (2019)
[55] Milio, E., A quasi-linear time algorithm for computing modular polynomials in dimension 2, LMS J. Comput. Math., 18, 1, 603-632 (2015) · Zbl 1371.11159
[56] Milne, J. S., Introduction to Shimura varieties, (Harmonic Analysis, the Trace Formula, and Shimura Varieties, vol. 4 (2005)), 265-378 · Zbl 1148.14011
[57] Morain, F., Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques, J. Théor. Nr. Bordx., 7, 255-282 (1995) · Zbl 0843.11030
[58] Müller, R., Hilbertsche modulformen und modulfunktionen zu \(\mathbb{Q}(\sqrt{ 8})\), Math. Ann., 266, 1, 83-103 (1983) · Zbl 0507.10022
[59] Müller, R., Hilbertsche Modulformen und Modulfunktionen zu \(\mathbb{Q}(\sqrt{ 5})\), Arch. Math., 45, 3, 239-251 (1985) · Zbl 0552.10016
[60] Mumford, D., Tata Lectures on Theta II, Progress in Mathematics, vol. 43 (1984), Birkhäuser · Zbl 0549.14014
[61] Nagaoka, S., On the ring of Hilbert modular forms over \(\mathbb{Z} \), J. Math. Soc. Jpn., 35, 4, 589-608 (1983) · Zbl 0517.10025
[62] Novocin, A.; Stehlé, D.; Villard, G., An LLL-reduction algorithm with quasi-linear time complexity, (Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing (2011), ACM), 403-412 · Zbl 1288.68294
[63] Resnikoff, H., On the graded ring of Hilbert modular forms associated with \(\mathbb{Q}(\sqrt{ 5})\), Math. Ann., 208, 161-170 (1974) · Zbl 0278.10029
[64] Robert, D., Computing cyclic isogenies using real multiplication, (Notes). ANR Peace meeting, Paris. Apr. 2013
[65] Rostovtsev, A.; Stolbunov, A., Public-key cryptosystem based on isogenies (2006), International Association for Cryptologic Research. Cryptology ePrint Archive
[66] Runge, B., Endomorphism rings of Abelian surfaces and projective models of their moduli spaces, Tohoku Math. J., 51, 3, 283-303 (1999) · Zbl 0972.14017
[67] Schoof, R., Counting points on elliptic curves over finite fields, J. Théor. Nr. Bordx., 7, 1, 219-254 (1995) · Zbl 0852.11073
[68] Serre, J.-P., Le Problème des Groupes de Congruence Pour \(\operatorname{S} \operatorname{L}_2\), Ann. Math., 92, 3, 489-527 (1970) · Zbl 0239.20063
[69] Smart, N., An analysis of Goubin’s refined power analysis attack, (Cryptographic Hardware and Embedded Systems-CHES 2003 (2003)), 281-290 · Zbl 1274.94116
[70] Smith, B., Isogenies and the discrete logarithm problem in Jacobians of genus 3 hyperelliptic curves, J. Cryptol., 22, 4, 505-529 (2009) · Zbl 1182.94047
[71] Streng, M., Complex multiplication of Abelian surfaces (2010), Universiteit Leiden, PhD thesis
[72] Streng, M., Computing Igusa class polynomials, Math. Comput., 83, 285, 275-309 (2014) · Zbl 1322.11066
[73] Sutherland, A., Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comput., 80, 273, 501-538 (2011) · Zbl 1231.11144
[74] Tate, J., Endomorphisms of Abelian varieties over finite fields, Invent. Math., 2, 133-144 (1966) · Zbl 0147.20303
[75] Teske, E., An elliptic curve trapdoor system, J. Cryptol., 19, 1, 115-133 (2006) · Zbl 1099.14012
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.