Computing Igusa class polynomials

Understand

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.