# Number of points on an elliptic curve

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: 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.

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.
• 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? Jul 21 at 9:36