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.