29
$\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$
3
  • $\begingroup$ check 'algorithm of schoof' :) (sry not time for long answer) $\endgroup$
    – Fleeep
    Sep 3, 2015 at 15:37
  • $\begingroup$ If we are given all the parameters of an elliptic curve (a, b, c, q, h=1) and also the order n. Can we confirm easily that the order given is the real one using the above mathematics? n = q+1-t, gives t, then we can test t directly with one of the equations in answers? $\endgroup$
    – user108420
    Mar 25 at 23:27
  • $\begingroup$ @user108420: We can verify that $t$ matches Hasses' bound, and we can verify that $n\,P=\mathcal O$ for some (or a few) random $P$, showing that $n$ is a multiple of the order of $P$, which must be the case for the actual $n$. For more (like probability of error, how the factorization of $n$ can be used to remove any doubt, reference on elliptic curve parameters validation), you might make a question (after searching if there's not a similar one). $\endgroup$
    – fgrieu
    Mar 26 at 8:05

2 Answers 2

29
$\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 $\ell$, there exist division polynomials $\psi_\ell\in\mathbb F_q[x]$ which vanish precisely on the $x$‑coordinates of the finite $\ell$‑torsion points of $E$. Therefore, one can compute $t\bmod\ell$ by checking for which $k\in\{0,\dots,\ell{-}1\}$ the functional equation $\varphi^2-k\varphi+q=0$ holds on a symbolic point $(x,y)$ where $x$ is a hypothetical root of $\psi_\ell$; in other words, this involves evaluating the endomorphism modulo $\psi_\ell$. The modular reduction is what makes this step polynomial‑time: The evaluation now works on symbolic points whose size is polynomially bounded in $\ell$, rather than (without any reduction) in $q$. Having computed $t\bmod\ell$ for a sufficiently large set $L$ of odd primes (according to Hasse's theorem, $\prod_{\ell\in L}\ell>4\sqrt q$ is enough), 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 popular computer algebra systems. Using SageMath, the number of $\mathbb F_{q^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_q$ can be computed as:

EllipticCurve(GF(q), [a1,a2,a3,a4,a6]).cardinality(extension_degree=n)
$\endgroup$
10
$\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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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