19
$\begingroup$

Let $\quad E:\; y^2 = x^3 + ax + b \quad$ be an elliptic curve defined over a finite field $\mathbb F_q$ where $q = p^n$, $a,b \in \mathbb F_q$ and $p \neq 2, 3$. By Hasse's theorem we know that the order of $E(\mathbb F_q)$ is in the range $[q+1-2\sqrt{q}, q+1+2\sqrt{q}]$.

Is it possible to determine the order of $E(\mathbb F_q)$ given $a, b, q$ without enumerating the points?

$\endgroup$
  • $\begingroup$ check 'algorithm of schoof' :) (sry not time for long answer) $\endgroup$ – Fleeep Sep 3 '15 at 15:37
20
$\begingroup$

There is a rather deep polynomial-time algorithm for counting the $\mathbb F_q$-rational points of an elliptic curve published by René Schoof in 1985 (with subsequent improvements by Noam Elkies and A. O. L. Atkin). It is based on two core ideas:

  • The number of points is closely linked to a functional equation $$ \varphi^2-t\varphi+q = 0 \qquad\in\operatorname{End}(E)$$ that the Frobenius endomorphism $$ \varphi\colon\;E\to E,\;\begin{cases}\mathcal O&\mapsto \mathcal O\\(x,y)&\mapsto (x^q,y^q) \end{cases} $$ satisfies in the endomorphism ring of $E$. If $t\in\mathbb Z$ is chosen such that this equation holds, it is called the trace of Frobenius and one can show that $$ \#E(\mathbb F_q)=q+1-t \text. $$ (The reason $\varphi$ has anything to do with point counting is that it leaves exactly the points with coordinates in $\mathbb F_q$ invariant.)
  • For odd $l$, there exist division polynomials $\psi_l\in\mathbb F_q[x]$ which vanish precisely on the $x$-coordinates of the finite $l$-torsion points of $E$. Therefore, one can compute $t\bmod l$ by checking for which $k\in\{0,\dots,l-1\}$ the functional equation $\varphi^2-t\varphi+q=0$ holds modulo $\psi_l$. Computing modulo $\psi_l$ greatly improves the complexity (compared to expanding the terms without any reduction). Having computed $t\bmod l$ for a sufficiently large (according to Hasse's theorem, $\prod_{l\in L}l>4\sqrt q$ is enough) set $L$ of odd primes, the Chinese remainder theorem can be used to reconstruct the trace of Frobenius $t$, thereby yielding the number of $\mathbb F_q$-rational points $\#E(\mathbb F_q)$ on $E$.

Of course, there are implementations of (the improved variants of) this algorithm in most computer algebra systems. Using sage, the number of $\mathbb F_{p^n}$-rational points of an elliptic curve $$ y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6 $$ defined over $\mathbb F_p$ can be computed as:

EllipticCurve(GF(p), [a1, a2, a3, a4, a6]).cardinality(extension_degree = n)
$\endgroup$
5
$\begingroup$

As yyyyyyy mentioned for counting number of points on elliptic curve over $\mathbb F_p$ we can use Elkies method. But for extension of fields use of this theorem make it so easy:

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$

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.