First we walk through the construction of MNT curves.
Set . Then it turns out
divides .
-
Pick a not too large and solve the following equation for :
-
Check is prime
-
Check 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 case works using cyclotomic polynomials.
Recall that , and that .
Then if the plus sign is chosen in the above example,
, and the order of the
curve is . Thus
and since we have hence the embedding
degree is indeed 6 by the BK theorem.
If the minus sign is chosen instead,
we have , ,
(recall )
which means the order of the curve is
. Hence
and since
we have that the embedding degree of the curve is 6.
Of course also divides but in general this is not
congruent
to so the embedding degree is not 3.
Note that can only be odd in the above cases if is even
which is why the MNT paper uses instead of our , which gives
. So if the above Pell-type equation is used,
a solution is useful only if .
The case from the MNT paper can also be explained in terms of
cyclotomic polynomials. Recall . Then taking
and so that yields
hence . When the minus sign is chosen, and the variable
is replaced by we match the parametrizations of the MNT paper exactly.
For , the MNT paper gives , for even ,
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
and .