E: $y^2+y=x^3$ an elliptic curve over $F_{2}$. How to prove the number of $E(F_{2^n})$ = $2^n+1$ if n is odd, ....

Question

Let E be the elliptic curve $y^2 + y = x^3$ over $F_2$. Prove

$ $#E($F_{2^n})$$ = \left\{ \begin{array}{ll} 2^n+1 & \quad n=odd \\ 2^n+1-2(-2)^{n/2} & \quad n=even \end{array} \right.$

I discovered $E(F_2)$ = {$\infty$ , (0,0), (0,1)} but from there I have no idea where to begin in honesty.

Answer 1

Theorem: Let #$E(Fq) = 1 - a + q $ Write $X_2 − aX + q = (X − α)(X − β)$. Then

# $E(F_{q^n}) = 1 − (α^n + β^n) + q^n $

for all n ≥ 1.

Now for the problem: It is easy. Write $x^2 + 2$ = $(x+i \sqrt2)(x-i \sqrt2)$ and so

#$ E(F_{2^n})=$ $2^n+1 -(x+i \sqrt2)(x-i \sqrt2)$

and from there it is then easy to use a phase argument to duduce the answer.

Note: $X_2 − aX + q$ is known as the Frobenius characteristic polynomial.