Class invariants by the CRT method

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

1 LFANT - Lithe and fast algorithmic number theory
2 IMB - Institut de Mathématiques de Bordeaux
3 Department of Mathematics [MIT]

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}$.

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

Andreas Enge, Andrew V. Sutherland. Class invariants by the CRT method. Ninth Algorithmic Number Theory Symposium ANTS-IX, Jul 2010, Nancy, France. pp.142-156, ⟨10.1007/978-3-642-14518-6_14⟩. ⟨inria-00448729v2⟩