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

Summary:

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

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

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

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\).