Programming ECC - Complex Multiplication

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 𝔽_{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 $𝔽_{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 = 4 r 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 $𝔽_{q}$ . There is no need to extend $𝔽_{q}$ at any time. However, many optimization cannot be applied, such as denominator elimination, and simplifying the formula for the Tate pairing.