3
$\begingroup$

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

$\endgroup$
3
  • 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$ 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$
4
  • 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$ 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.