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.