Cryptology ePrint Archive: Report 2010/031

Class Invariants by the CRT Method

Andreas Enge and Andrew V. Sutherland

Abstract: 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}.

Category / Keywords: public-key cryptography / elliptic curve cryptography, complex multiplication

Date: received 20 Jan 2010

Contact author: drew at math mit edu

Available formats: PDF | BibTeX Citation

Version: 20100122:035918 (All versions of this report)

Discussion forum: Show discussion | Start new discussion