## Complex Multiplication

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

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

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

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

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.

*blynn@cs.stanford.edu*💡