How to count number of rational points on elliptic curve over binary field?
$\begingroup$
$\endgroup$
3
1 Answer
$\begingroup$
$\endgroup$
4
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$.
answered Jan 3, 2016 at 19:17
-
1$\begingroup$ Would you mind sharing a link to the proof of this theorem? $\endgroup$– SEJPMJan 3, 2016 at 19:21
-
1$\begingroup$ This theorem is theorem3.11 in "Guide to Elliptic Curve Cryptography" page 83. Unfortunately the proof of this theorem is not in that book. $\endgroup$ Jan 3, 2016 at 19:45
-
$\begingroup$ The book can be found here math.boisestate.edu/~liljanab/MATH508/… (I think this is a legal link) $\endgroup$ Jan 4, 2016 at 8:52
-
1$\begingroup$ @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})$. $\endgroup$– yyyyyyyJan 9, 2016 at 23:45
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. $\endgroup$