Class invariants by the CRT method

Andreas Enge (1) , Andrew V. Sutherland (2)

1 LFANT - Lithe and fast algorithmic number theory
2 Department of Mathematics [MIT]

We adapt the CRT approach to 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}$.

Domaines: Théorie des nombres [math.NT]

Andreas Enge, Andrew V. Sutherland. Class invariants by the CRT method. 2010. ⟨inria-00448729v1⟩