Computing class polynomials with the Chinese Remainder Theorem

Опубликовано 8 сентября 2016, 17:05

Class polynomials play a key role in the CM-method for constructing elliptic curves with known order. This has many applications to cryptography and is the primary means of obtaining pairing-friendly curves. The CM-method is unfortunately constrained by practical limits on the size of the CM discriminant, with |D| < 10^10 an accepted upper bound. I will present a new algorithm, based on the CRT-approach to computing Hilbert class polynomials [Belding-Broker-Enge-Lauter 2008], one that is faster than existing methods and able to handle much larger discriminants. For suitable D, this algorithm can also compute class polynomials for more favorable class invariants (derived from those of Weber and Ramanujan), yielding a further improvement in the constant factors. These results have been used to construct many pairing-friendly curves with large CM-discriminant, including examples with |D| > 10^14.