In his paper on pairing based cryptography, Menezes claims that for $$ E_1: y^2+y = x^3+x+1 $$ the number of $\mathbb{F}_{2^m}$-points is $2^m +1 - (1+i)^m - (1-i)^m$. Whereas this is clear, it is not clear to me how he reaches this conclusion:

enter image description here

In addition, I also do not see why it is relevant (and how one sees/arrives at this relevancy) to express $2^m +1 - (1+i)^m - (1-i)^m$ depending on m mod 8.


1 Answer 1


This follows from the identity \begin{eqnarray}(1+i)^m+(1-i)^m&=&(\sqrt 2(\exp(i\pi/4))^m+(\sqrt 2(\exp(-i\pi/4))^m\\ &=&2^{m/2}(\exp(im\pi/4)+\exp(-im\pi/4))\end{eqnarray} which by Euler's formula is $$2^{m/2}2\cos(m\pi/4).$$

Now note that $2^{m/2}2=2\sqrt q$ and that $$\cos(m\pi/4)=\cases{1&$m\equiv 0\pmod 8$ \\ 1/\sqrt2&$m\equiv \pm1\pmod 8$\\ 0&$m\equiv\pm2\pmod 8$\\ -1/\sqrt2&$m\equiv\pm3\pmod 8$\\ -1&$m\equiv 4\pmod 8$}.$$

The reason for this expression is that checking the congruence class of $m\pmod 8$ and then computing a power of 2 is a simpler computation than $(1+i)^m+(1-i)^m$. These expressions also lend themselves more readily to confirming the necessary conditions for a pairing-friendly curve of various embedding degrees.

  • $\begingroup$ Say I would want to do something similar for $E_2:y^2 = x^3-x+1$ over $\mathbb{F}_{3^m}$. How would I proceed? $\endgroup$ Jul 21 at 9:36
  • $\begingroup$ Your comment would be best asked as a follow on question. $\endgroup$
    – Daniel S
    Jul 21 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.