MNT Curves

First we walk through the construction of k=6 MNT curves. Set q=l2+1,t=±l+1. Then it turns out q+1t divides q61.

The CM equation becomes DV2=3l2±2l+3. If we write U=3l±1 we have an easily solved generalized Pell equation

U23DV2=8

Summary:

  • Pick a D not too large and solve the following equation for V,l:

    DV2=3l2±2l+3
  • Check q=l2+1 is prime

  • Check qt+1=q±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)=l2l+1, and that Φ6(l)|l61. Then if the plus sign is chosen in the above example, q=Φ6(l)+l, and the order of the curve is n=qt+1=Φ6(l). Thus

q61=l61modn

and since n|l61 we have n|q61 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)=l2+l+1) which means the order of the curve is n=Φ3(l). Hence

q61=(l)61=l61modn

and since Φ3(l)|l61 we have that the embedding degree of the curve is 6. Of course Φ3(l) also divides l31 but in general this is not congruent to (l)31 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=4l2+1,t=1±2l. So if the above Pell-type equation is used, a solution U is useful only if U=1,5(mod6).

The k=4 case from the MNT paper can also be explained in terms of cyclotomic polynomials. Recall Φ4(l)=l2+1. Then taking q=Φ4(l)±l and t=±l+1 so that n=Φ4(l) yields

q41=(±l)41(modn)

hence n|q41. 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=3l21, t=1±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 💡