Complex multiplication

Complex multiplication (CM) is a method which utilizes class field theory in order to generate curves with a prescribed order. Namely, if 

and $j$ is a root of the $D$-th Hilbert class polynomial modulo $q$ (which is a prime), then any curve with j-invariant $j$ (or its quadratic twist) will have order $q+1+t$ over $\mathbb{F}_q$. Given the j-invariant, such a curve can be easily constructed: for example, we can define it by the Weierstrass equation

where $k = j / (1728 - j)$ and $c \in \mathbb{F}_q$ is arbitrary. (Note that this does not work for the special cases $j=0$ and $j=1728$, which correspond to curves given by $y^2 = x^3 - 1$ and $y^2 = x^3 - x$, respectively.) The bottleneck is the Hilbert polynomial computation, which allows us to only use a small $D$ (currently up to around 44 bits). In particular, every curve generated by the CM method will necessarily have a small $D$ (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.

References

• 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.