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 💡