Class invariants by the CRT method

Abstract

We adapt the CRT approach for computing Hilbert class polynomials to handle a wide range of class invariants. For suitable discriminants D, this improves its performance by a large constant factor, more than 200 in the most favourable circumstances. This has enabled record-breaking constructions of elliptic curves via the CM method, including examples with |D|>10^15.

15 pages, final version, to appear in ANTS IX (Algorithmic Number Theory Symposium, 2010)

References in corpus (3)

• Computing the endomorphism ring of an ordinary elliptic curve over a finite field
• Computing Hilbert Class Polynomials
• Generalised Weber Functions

Cited by in corpus (12)

• Isogeny volcanoes
• Class polynomials for nonholomorphic modular functions
• Accelerating the CM method
• $\ell$-adic images of Galois for elliptic curves over $\mathbb{Q}$
• Computing classical modular forms
• A quasi-linear time algorithm for computing modular polynomials in dimension 2
• On the evaluation of modular polynomials
• Heuristics on pairing-friendly abelian varieties
• There are at most finitely many singular moduli that are S-units
• Computing the endomorphism ring of an elliptic curve over a number field
• Cycles of supersingular elliptic curves for pairing-based proof systems
• Hard isogeny problems over RSA moduli and groups with infeasible inversion