Hilbert class polynomials

For a negative discriminant $D$ (that is, $D < 0$ and $D \equiv 0, 1 \pmod 4$), the Hilbert class polynomial is

where $(a,b,c)$ ranges over the primitive reduced positive definite binary quadratic forms $ax^2 + bxy + cy^2$ of discriminant $b^2 - 4ac = D$. It has integer coefficients and degree equal to the class number $h(D)$, and its roots generate the ring class field of the order of discriminant $D$ [Coh1996]. It is used to construct elliptic curves with complex multiplication, for instance in elliptic curve primality proving.

acb_modular_hilbert_class_poly computes $H_D$ numerically [Enge2009]:

1. It enumerates the reduced forms with $|b| \le a \le c$ [Coh1996, Algorithm 5.3.5], pairing $(a, b, c)$ with $(a, -b, c)$, whose roots are complex conjugate.
2. It estimates the bit size of the coefficients from $\log |H_D(0)| \lesssim \pi \sqrt{|D|} \sum 1/a$ and chooses a working precision 0.5% above it, plus 20 bits.
3. It evaluates the roots with acb_modular_j, forming a real quadratic factor $x^2 - 2\operatorname{Re}(j) x + |j|^2$ for each conjugate pair, and multiplies the factors by binary splitting with arb_poly_mul, in parallel with flint_parallel_binary_splitting when several threads are available.
4. It converts the result with arb_poly_get_unique_fmpz_poly. Since the real polynomial is an enclosure of $H_D$, this succeeds only when every coefficient ball contains a unique integer, and then the result is proven correct. If the enclosure is too wide, it prints a message to standard output and retries with 1.2 times the precision.

Each $j$-value costs $O(\sqrt{p})$ multiplications at precision $p$, and $p$ grows like $\sqrt{|D|} \log |D|$; this simple method is practical for discriminants up to several million. Faster methods for large $D$ use class invariants smaller than $j$ (Weber functions and other modular functions) and the Chinese remainder theorem [EngeCM].

If $D \ge 0$ or $D \equiv 2, 3 \pmod 4$, the output is the zero polynomial.

Example#

The class polynomial of discriminant $-23$ (class number 3), the size of the class polynomial of discriminant $-1000003$, and the near-integer $j((1 + \sqrt{-163})/2) = -640320^3$ for the class number one discriminant $-163$.

#include <flint/fmpz_poly.h>
#include <flint/acb.h>
#include <flint/acb_modular.h>

int main(void)
{
    fmpz_poly_t H;
    acb_t tau, j;

    fmpz_poly_init(H);
    acb_init(tau);
    acb_init(j);

    acb_modular_hilbert_class_poly(H, -23);
    fmpz_poly_print_pretty(H, "x");
    flint_printf("\n");

    acb_modular_hilbert_class_poly(H, -1000003);
    flint_printf("D = -1000003: degree %wd, %wd bits\n",
        fmpz_poly_degree(H), FLINT_ABS(fmpz_poly_max_bits(H)));

    arb_set_ui(acb_imagref(tau), 163);
    arb_sqrt(acb_imagref(tau), acb_imagref(tau), 128);
    arb_one(acb_realref(tau));
    acb_mul_2exp_si(tau, tau, -1);
    acb_modular_j(j, tau, 128);
    acb_printn(j, 30, 0);
    flint_printf("\n");

    fmpz_poly_clear(H);
    acb_clear(tau);
    acb_clear(j);
    return 0;
}

x^3+3491750*x^2-5151296875*x+12771880859375
D = -1000003: degree 105, 8527 bits
[-262537412640768000.000000000000 +/- 2.85e-19]