Computing Hilbert class polynomials with the Chinese Remainder Theorem

Abstract

We present a space-efficient algorithm to compute the Hilbert class polynomial H_D(X) modulo a positive integer P, based on an explicit form of the Chinese Remainder Theorem. Under the Generalized Riemann Hypothesis, the algorithm uses O(|D|^(1/2+o(1))log P) space and has an expected running time of O(|D|^(1+o(1)). We describe practical optimizations that allow us to handle larger discriminants than other methods, with |D| as large as 10^13 and h(D) up to 10^6. We apply these results to construct pairing-friendly elliptic curves of prime order, using the CM method.

37 pages, corrected a typo that misstated the heuristic complexity

Cited by in corpus (15)

• Isogeny volcanoes
• Computing images of Galois representations attached to elliptic curves
• Class polynomials for nonholomorphic modular functions
• Accelerating the CM method
• Identifying supersingular elliptic curves
• $\ell$-adic images of Galois for elliptic curves over $\mathbb{Q}$
• A quasi-linear time algorithm for computing modular polynomials in dimension 2
• On the evaluation of modular polynomials
• Computing separable isogenies in quasi-optimal time
• Constructing supersingular elliptic curves with a given endomorphism ring
• On the Distribution of Atkin and Elkies Primes
• Degree and height estimates for modular equations on PEL Shimura varieties
• Cycles of supersingular elliptic curves for pairing-based proof systems
• Computing the endomorphism ring of an elliptic curve over a number field
• Finding elliptic curves with a subgroup of prescribed size