Computing class polynomials with the Chinese Remainder Theorem

  • Drew Sutherland | MIT

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| < 1010 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| > 1014.

Speaker Details

Andrew Sutherland is a Research Scientist in the mathematics department at MIT, with a passion for computational number theory. His work includes results for elliptic and hyperelliptic curves, ideal class groups, and generic group algorithms. He received his PhD from MIT in 2007, following a successful career as an entrepreneur in the software industry.

Watch Next