Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-28T04:33:04.779Z Has data issue: false hasContentIssue false
  • English
  • Français

Modular Polynomials for Genus 2

Published online by Cambridge University Press:  01 February 2010

Reinier Bröker  and
Kristin Lauter
Reinier Bröker
Affiliation:
Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA, [email protected]
Kristin Lauter
Affiliation:
Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA, [email protected]

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.

Modular polynomials are an important tool in many algorithms involving elliptic curves. In this article we investigate their generalization to the genus 2 case following pioneering work by Gaudry and Dupont. We prove various properties of these genus 2 modular polynomials and give an improved way to explicitly compute them.

Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 12 , 2009 , pp. 326 - 339
Copyright
Copyright © London Mathematical Society 2009

References

1.Andrianov, A. N. and Zhuravlev, V. G., Modular forms and Hecke operators, AMS Translations of mathematical monographs, vol 145 (AMS, Providence, 1995).Google Scholar
2.Artin, E., Geometric algebra, Wiley Classics Library (John Wiley & Sons Inc., New York, 1988).Google Scholar
3.Baily, W. L. and Borel, A., ‘Compactification of arithmetic quotients of bounded symmetric domains’, Ann. of Math. 84 (1966) 442–538.CrossRefGoogle Scholar
4.Belding, J., Bröker, R., Enge, A. and Lauter, K., ‘Computing Hilbert Class Polynomials’, Algorithmic Number Theory Symposium VIII, Banff, 2008, ed. van der Poorten, A. J. and Stein, A. (Springer Lecture Notes in Computer Science 5011, Berlin, 2008) 282–295.CrossRefGoogle Scholar
5.Birkenhake, C. and Lange, C., Complex Abelian Varieties, Grundlehren der Mathematischen Wissenschaften 302 (Springer, Berlin, 2003).Google Scholar
6.Bost, J.-B. and Mestre, J.-F., ‘Moyenne arithmético-géometrique et périodes de courbes de genre 1 et 2’, Gaz. Math. Soc. France 38 (1988) 36–64.Google Scholar
7.Chai, C.-L. and Norman, P., ‘Bad reduction of the Siegel moduli scheme of genus two with Γ0(p)-level structure’, Amer. J. Math. 122 (1990) 1003–1071.CrossRefGoogle Scholar
8.Cohen, H., Frey, G. et al. , Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and Its Applications 34 (Chapman & Hall/CRC, Boca Raton, 2006).Google Scholar
9.Cox, D. A., Primes of the form x2 + ny2, 1st edn (John Wiley & Sons Inc., New York, 1989).Google Scholar
10.Dupont, R., Moyenne arithmético-géométrique, suites de Borchardt et applications, PhD-thesis (École Polytechnique, Paris, 2006).Google Scholar
11.Eichler, M. and Zagier, D., The theory of Jacobi forms, Progress in mathematics 55 (Birkhäuser, Boston, 1985).CrossRefGoogle Scholar
12.Eisenträger, K. and Lauter, K., ‘A CRT algorithm for constructing genus 2 curves over finite fields’, Arithmetic, Geometry and Coding Theory (AGCT-10), online at http://arxiv.org/abs/math.NT/0405305 (2005).Google Scholar
13.Enge, A. and Morain, F., SEA in genus 1: 2500 decimal digits, Announcement sent to the Number theory mailing list, online available at http://listserv.nodak.edu/archives/nmbrthry.html (December 2006).Google Scholar
14.Gaudry, P., Algorithmique des courbes hyperelliptiques et applications à la cryptologie, PhD-thesis (École Polytechnique, Paris, 2000).Google Scholar
15.Gaudry, P. and Harley, R., ‘Counting points on hyperelliptic curves over finite fields’, Algorithmic Number Theory Symposium IV, Leiden, 2000, ed. Bosma, W. (Springer Lecture Notes in Computer Science 1838, Berlin, 2000) 313–332.Google Scholar
16.Gaudry, P., Houtmann, T., Kohel, D., Ritzenthaler, C. and Weng, A., ‘The 2-adic CM-method for genus 2 curves with applications to cryptography’, Advances in Cryptology, Asiacrypt 2006, Shanghai, 2006, ed. Lai, X. and Chen, K. (Springer Lecture Notes in Computer Science 4284, Berlin, 2006) 114–129.CrossRefGoogle Scholar
17.Gaudry, P. and Schost, E., ‘Modular equations for hyperelliptic curves’, Math. Comp. 74 (2005) 429–454.Google Scholar
18.Igusa, J.-I., ‘On Siegel modular forms of genus two’, Amer. J. Math. 84 (1962) 175–200.CrossRefGoogle Scholar
19.King, O. H., ‘The subgroup structure of finite classical groups in terms of geometric configurations’, Surveys in Combinatorics, ed. Webb, B. S., London Mathematical Society Lecture Note Series 327 (Cambridge University Press, Cambridge, 2005) 29–56.Google Scholar
20.Koecher, M., ‘Zur Theorie der Modulfunktionen n-ten Grades, I’, Math. Z. 59 (1954) 399–416.CrossRefGoogle Scholar
21.Magaard, K., Shaska, T. and VölkleinT, H. T, H., ‘Genus 2 curves with degree 5 elliptic subcovers’, (Form Math., to appear).Google Scholar
22.Mestre, J.-F., ‘Construction des courbes de genre 2 à partir de leurs modules’, Effective methods in algebraic geometry, Livorno, 1990, ed. Mora, T. and Traverso, C. (Birkhäuser Progress in Mathematics 94, Boston, 1991) 313–334.CrossRefGoogle Scholar
23.Murabayashi, N., ‘The moduli space of curves of genus two covering elliptic curves’, Manuscripta Math. 84 (1994) 125–133.Google Scholar
24.Schoof, R., ‘Counting points on elliptic curves over finite fields’, J. Théor. Nombres Bordeaux 7 (1993) 219–254.Google Scholar
25.Schoof, R., ‘Elliptic curves over finite field and the computation of square roots mod p’, Math. Comp. 44 (1985) 483–494.Google Scholar
26.Shaska, T., ‘Genus 2 curves covering elliptic curves, a computational approach’, Lect. Notes in Comp. 13 (2005) 243–255.Google Scholar
27.Shaska, T., ‘Genus 2 fields with degree 3 elliptic subfields’, Forum Math. 16 no. 2 (2004) 263–280.Google Scholar
28.Sutherland, A. V., ‘Computing Hilbert class polynomials with the Chinese Remainder Theorem’, available at http://arxiv.org/abs/0903.2785 (2009).Google Scholar