Programming ECC - MNT Curves

MNT Curves

First we walk through the construction of $k = 6$ MNT curves. Set $q = l^{2} + 1, t = \pm l + 1$ . Then it turns out $q + 1 - t$ divides $q^{6} - 1$ .

The CM equation becomes $D V^{2} = 3 l^{2} \pm 2 l + 3$ . If we write $U = 3 l \pm 1$ we have an easily solved generalized Pell equation

U^{2} - 3 D V^{2} = - 8

Summary:

Pick a $D$ not too large and solve the equation
DV 2 =3 l 2 ±2 l+3
```
for +++ $V, l$ +++
```
Check $q = l^{2} + 1$ is prime
Check $q - t + 1 = q \pm l$ has a large prime factor
Check the embedding degree is not less than 6 (very likely)
Use CM method to construct the curve

We can explain how the $k = 6$ case works using cyclotomic polynomials. Recall that $Φ_{6} (l) = l^{2} - l + 1$ , and that $Φ_{6} (l) ∣ l^{6} - 1$ . Then if the plus sign is chosen in the above example, $q = Φ_{6} (l) + l$ , and the order of the curve is $n = q - t + 1 = Φ_{6} (l)$ . Thus

q^{6} - 1 = l^{6} - 1 \mod n

and since $n ∣ l^{6} - 1$ we have $n ∣ q^{6} - 1$ hence the embedding degree is indeed 6 by the BK theorem.

If the minus sign is chosen instead, we have $q = Φ_{3} (l) - l$ , $t = - l + 1$ , (recall $Φ_{3} (l) = l^{2} + l + 1$ ) which means the order of the curve is $n = Φ_{3} (l)$ . Hence

q^{6} - 1 = (- l)^{6} - 1 = l^{6} - 1 mod n

and since $Φ_{3} (l) ∣ l^{6} - 1$ we have that the embedding degree of the curve is 6. Of course $Φ_{3} (l)$ also divides $l^{3} - 1$ but in general this is not congruent to $(- l)^{3} - 1$ so the embedding degree is not 3.

Note that $q$ can only be odd in the above cases if $l$ is even which is why the MNT paper uses $2 l$ instead of our $l$ , which gives $q = 4 l^{2} + 1, t = 1 \pm 2 l$ . So if the above Pell-type equation is used, a solution $U$ is useful only if $U = 1, 5 (mod 6)$ .

The $k = 4$ case from the MNT paper can also be explained in terms of cyclotomic polynomials. Recall $Φ_{4} (l) = l^{2} + 1$ . Then taking $q = Φ_{4} (l) \pm l$ and $t = \pm l + 1$ so that $n = Φ_{4} (l)$ yields

q^{4} - 1 = (\pm l)^{4} - 1 (mod n)

hence $n ∣ q^{4} - 1$ . When the minus sign is chosen, and the variable $l$ is replaced by $l + 1$ we match the parametrizations of the MNT paper exactly.

For $k = 3$ , the MNT paper gives $q = 3 l^{2} - 1$ , $t = - 1 \pm 3 l$ for even $l$ , but it is not obvious how these are related to cyclotomic polynomials.

Note the MNT paper goes further: it shows that aside from supersingular curves, these are the only parametrizations that lead to embedding degrees $3, 4$ and $6$ .