Computing Igusa class polynomials
From MaRDI portal
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. The algorithm is basically the complex analytic method of Spallek and van Wamelen, and we show that it finishes in time Otilde(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.
Recommendations
- Computing class polynomials for abelian surfaces
- Computing Hilbert Class Polynomials
- The complexity of class polynomial computation via floating point approximations
- Igusa class polynomials, embeddings of quartic CM fields, and arithmetic intersection theory
- Improved CRT algorithm for class polynomials in genus 2
Cites work
- A CRT algorithm for constructing genus 2 curves over finite fields
- A p-Adic Quasi-Quadratic Time Point Counting Algorithm
- Approximating rings of integers in number fields
- Arithmetic intersection on a Hilbert modular surface and the Faltings height
- Arithmetic variety of moduli for genus two
- Class invariants for quartic CM fields
- CM-values of Hilbert modular functions
- Computing Arakelov class groups
- Computing Hilbert Class Polynomials
- Constructing hyperelliptic curves of genus 2 suitable for cryptography
- Divisibility sequences for elliptic curves with complex multiplication
- Examples of genus two CM curves defined over the rationals
- Explicit Lower bounds for residues at đ =1 of Dedekind zeta functions and relative class numbers of CM-fields
- Explizite Bestimmung der Randflächen des Fundamentalbereiches der Modulgruppe zweiten Grades
- Fast Decomposition of Polynomials with Known Galois Group
- Fast evaluation of modular functions using Newton iterations and the AGM
- Fast multiplication and its applications
- Field of moduli and field of definition for curves of genus 2
- Genus 2 curves with complex multiplication
- Higher-dimensional 3-adic CM construction
- scientific article; zbMATH DE number 5532102 (Why is no real title available?)
- scientific article; zbMATH DE number 3181290 (Why is no real title available?)
- scientific article; zbMATH DE number 3760283 (Why is no real title available?)
- scientific article; zbMATH DE number 16657 (Why is no real title available?)
- scientific article; zbMATH DE number 44586 (Why is no real title available?)
- scientific article; zbMATH DE number 1936673 (Why is no real title available?)
- scientific article; zbMATH DE number 1852135 (Why is no real title available?)
- scientific article; zbMATH DE number 2120946 (Why is no real title available?)
- scientific article; zbMATH DE number 870534 (Why is no real title available?)
- scientific article; zbMATH DE number 3061635 (Why is no real title available?)
- Modular Forms and Projective Invariants
- On certain reduction problems concerning abelian surfaces
- On Siegel Modular Forms of Genus Two
- On special values of theta functions of genus two
- Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
- Tata lectures on theta. II: Jacobian theta functions and differential equations. With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman, and H. Umemura
- The 2-Adic CM Method for Genus 2 Curves with Application to Cryptography
- The complexity of class polynomial computation via floating point approximations
Cited in
(24)- Gauge theories and dessins d'enfants: beyond the torus
- On different expressions for invariants of hyperelliptic curves of genus 3
- Isogeny graphs with maximal real multiplication
- A CM construction for curves of genus 2 with \(p\)-rank 1
- Computing genus 2 curves from invariants on the Hilbert moduli space
- Computing class polynomials for abelian surfaces
- Examples of CM curves of genus two defined over the reflex field
- Improved CRT algorithm for class polynomials in genus 2
- The complexity of class polynomial computation via floating point approximations
- Finding elliptic curves with a subgroup of prescribed size
- Evaluating Igusa functions
- Plane quartics over \(\mathbb {Q}\) with complex multiplication
- Spanning the isogeny class of a power of an elliptic curve
- Isogenous hyperelliptic and non-hyperelliptic Jacobians with maximal complex multiplication
- A bound on the primes of bad reduction for CM curves of genus 3
- Genus-2 curves and Jacobians with a given number of points
- Computing Hilbert Class Polynomials
- Genus 3 hyperelliptic curves with CM via Shimura reciprocity
- Certified Newton schemes for the evaluation of low-genus theta functions
- The complex multiplication method for genus 3 curves
- Computing isogenies from modular equations in genus two
- Schertz style class invariants for higher degree CM fields
- Branes, U-folds and hyperelliptic fibrations
- Modular polynomials on Hilbert surfaces
This page was built for publication: Computing Igusa class polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2862530)
