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.
