# Counting points on elliptic curve over binary field

How to count number of rational points on elliptic curve over binary field?

• My answer to this question might help. Schoof's algorithm applies (incorporating some special cases concerning the division polynomials) equally to finite fields of characteristic $2$ or $3$. Jan 3, 2016 at 13:10
• Can you provide me with any example of finding such number with this algorithm? Jan 3, 2016 at 13:52
• Well, one can imagine from looking at the description that it is extremely laborious to execute the algorithm by hand. (Read: I would not want to do this.) If you only need the result of the computation, I suggest using an implementation from a computer algebra package like sage, as recommended in my linked post. If this is some kind of assignment you have to do by hand, I suspect there is an easier method for your special case than invoking a generic algorithm. Jan 3, 2016 at 16:24

Counting number of points on elliptic curve over $\mathbb F_2$ is very easy.For extension of fields we can use of this theorem:
Theorem : Let $E$ be an elliptic curve defined over $F_q$, and let $\#E(F_q ) = q +1−t$. Then $\#E(F_{q^n} ) = q^n + 1 − V_n$ for all $n ≥ 2$, where $\{V_n\}$ is the sequence defined recursively by $V_0 = 2, V_1 = t$, and $V_n = V_1V_{n−1}−qV_{n−2}$ for $n ≥ 2$.
• @SEJPM This is a consequence to Silverman's Arithmetic of Elliptic Curves, theorem V.2.3.1(a), stating that $\#E(\mathbb F_{q^n})=q^n+1-\alpha^n-\beta^n$ for the roots $\alpha,\beta\in\mathbb C$ of the polynomial $\xi^2-t\xi+q\in\mathbb Z[\xi]$. Using $\alpha+\beta=t$ and $\alpha\beta=q$, one easily proves by induction on the recursive definition of the $V_n$ that $\alpha^n,\beta^n$ are the roots of $\xi^2-V_n\xi+q^n\in\mathbb Z[\xi]$, therefore $V_n=\alpha^n+\beta^n$, which is nothing but $q^n+1-\#E(\mathbb F_{q^n})$. Jan 9, 2016 at 23:45