## Complex Multiplication

The CM (Complex Multiplication) method of generating an elliptic curve starts with an integer equation

$D V^2 = 4 q - t^2$

where $$q$$ is prime. Then let $$j$$ be any root of the Hilbert polynomial $$H_D(x)$$ modulo $$q$$. If $$j = 0$$ or $$j = 1728$$ we wind up with special curves ($$y^2 = x^3 - 1$$, $$y^2 = x^3 - x$$ respectively) which are discussed elsewhere.

Set $$k = j / (1728 - j)$$ (modulo $$q$$). Then the curve

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

has $$j$$-invariant $$j$$ for any nonzero $$c \in \mathbb{F}_q$$. Let us first pick $$c=1$$. Then this curve has order $$q + t + 1$$ or $$q - t + 1$$. Choose a random point and multiply by $$q - t + 1$$ and check if the result is $$O$$. If not, then the curve must have order $$q + t + 1$$, in which case we pick $$c$$ to be some quadratic nonresidue in $$\mathbb{F}_q$$, and we now have a curve with order $$q - t + 1$$. Thus using the above equation and a Hilbert polynomial it is easy to write down a curve with a certain order over a certain field.

### Example

Let $$t = 2$$. Let $$r$$ be a prime and suppose $$q = 28 r^2 h^2 + 1$$ is also prime for some $$h$$. Take $$D = 7$$. Then the CM equation becomes

$7 V^2 = 4 (28 (r h)^2 + 1) - 4$

which has the solution $$V = 4r h$$. It turns out that $$H_7(x) = x + 3375$$, so set $$k = -3375 / (1728 - 3375)$$ (mod $$q$$) and write down the curve

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

Check if this has order $$q - t + 1 = q - 1$$. If not, take the twist of this curve instead.

Now we have a curve with order $$q - 1 = 28 (r h)^2$$. We shall see later that since $$r$$ divides $$q-1$$, we can implement a pairing for this curve over $$\mathbb{F}_q$$. There is no need to extend $$\mathbb{F}_q$$ at any time. However, many optimization cannot be applied, such as denominator elimination, and simplifying the formula for the Tate pairing.

Ben Lynn blynn@cs.stanford.edu 💡