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 = 3l \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

    \[ D V^2 = 3 l^2 \pm 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 $\Phi_6(l) = l^2 - l + 1$, and that $\Phi_6(l) | l^6 - 1$. Then if the plus sign is chosen in the above example, $q = \Phi_6(l) + l$, and the order of the curve is $n = q - t + 1 = \Phi_6(l)$. Thus

\[q^6 - 1 = l^6 - 1 \bmod 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 = \Phi_3(l) - l$, $t = -l + 1$, (recall $\Phi_3(l) = l^2 + l + 1$) which means the order of the curve is $n = \Phi_3(l)$. Hence

\[q^6-1 = (-l)^6 - 1 = l^6 - 1 \bmod n\]

and since $\Phi_3(l) | l^6 - 1$ we have that the embedding degree of the curve is 6. Of course $\Phi_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 $2l$ instead of our $l$, which gives $q = 4l^2+1, t = 1 \pm 2l$. So if the above Pell-type equation is used, a solution $U$ is useful only if $U = 1, 5 \pmod{6}$.

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

\[ q^4 - 1 = (\pm l)^4 - 1 \pmod{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 = 3l^2 - 1$, $t=-1\pm 3l$ 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$.