Complex multiplication (CM) is a method which utilizes class field theory in order to generate curves with a prescribed order. Namely, if
and is a root of the -th Hilbert class polynomial modulo (which is a prime), then any curve with j-invariant (or its quadratic twist) will have order over . Given the j-invariant, such a curve can be easily constructed: for example, we can define it by the Weierstrass equation
where and is arbitrary. (Note that this does not work for the special cases and , which correspond to curves given by and , respectively.) The bottleneck is the Hilbert polynomial computation, which allows us to only use a small (currently up to around 44 bits). In particular, every curve generated by the CM method will necessarily have a small (called CM discriminant), which means its ring of endomorphisms can be efficiently constructed. Apart from a slight speed-up of scalar multiplication, it is not known whether this significantly impacts security, but such curves certainly cannot be considered random.
- Stanford crypto notes
- Andrew Sutherland: Computing Hilbert class polynomials with the Chinese remainder theorem
- Daniel J. Bernstein, Tanja Lange: SafeCurves: choosing safe curves for elliptic-curve cryptography, accessed 12 October 2020.