Skip to main content

Standard curve database


Complex multiplication

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

Ds2=4qt2Ds^2 = 4 q - t^2

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

y2=x3+3kc2x+2kc3,y^2 = x^3 + 3 k c^2 x + 2 k c^3,

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


© 2020 Jan Jancar | Built with Dox theme for Gatsby