3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – yyyyyyy Jan 3 '16 at 13:10
  • $\begingroup$ Can you provide me with any example of finding such number with this algorithm? $\endgroup$ – ColdAsDomino Jan 3 '16 at 13:52
  • $\begingroup$ 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. $\endgroup$ – yyyyyyy Jan 3 '16 at 16:24
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Would you mind sharing a link to the proof of this theorem? $\endgroup$ – SEJPM Jan 3 '16 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$ – Meysam Ghahramani Jan 3 '16 at 19:45
  • $\begingroup$ The book can be found here math.boisestate.edu/~liljanab/MATH508/… (I think this is a legal link) $\endgroup$ – ddddavidee Jan 4 '16 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$ – yyyyyyy Jan 9 '16 at 23:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.