Search

## Complex multiplication

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

$Ds^2 = 4 q - t^2$

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

$y^2 = x^3 + 3 k c^2 x + 2 k c^3,$

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

© 2020 Jan Jancar | Built with Dox theme for Gatsby