Computing Class Polynomials for Abelian Surfaces

Abstract

We describe a quasilinear algorithm for computing Igusa class polynomials of Jacobians of genus-2 curves via complex floating-point approximations of their roots. After providing an explicit treatment of the computations in quartic CM fields and their Galois closures, we pursue an approach due to Dupont for evaluating ϑ-constants in quasilinear time using Newton iterations on the Borchardt mean. We report on experiments with our implementation and present an example with class number 20 016.

2000 AMS Subject Classification::

• 11Y40
• 11G10
• 14K22
• 14K25
• 14G50

Keywords::

• algebraic number theory computations
• abelian varieties of dimension >1
• complex multiplication
• theta functions
• applications to coding theory and cryptography

Notes

¹Available at http://echidna.maths.usyd.edu.au/echidna/dbs/complex_multiplication2.html.

²Such a quadratic, yet efficient, implementation was used by T. Houtmann to compute class polynomials of degree up to 500 (personal communication; no reference exists).