## 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$$.

Ben Lynn blynn@cs.stanford.edu 💡