I want to find the order of elliptic curve over the finite field extension $\mathbb{F}_{p^2}$, where $E(\mathbb{F}_{p^2}):y^2=x^3+ax+b $

I am using the method illustrated by John J. McGee in his thesis 2006. Where $\#E(\mathbb{F}_{p^n})=p^n+1-(s_{n})$, with, $s_0=2$, $s_1=t$ and $s_{n+1}=t s_n - ps_{n-1}$.

Finding $t$ is easy by using Weil's theorem, where $\#E(\mathbb{F}_p)=p+1-t.$

McGee had put $s_0=2$, but he did not say why, nor he gave a reference. Therefore my question is: What is the condition to determine $s_0$? Is it supposed to be $2$ at all cases? And Why? I am asking this, because I worked on few examples where I found the number of points is not the same order when $s_0=2$.

Worth to say, the method that I am using to find the points of $E(\mathbb{F}_{p^2})$ is the same method to find the point of elliptic curve over $\mathbb{F}_p$.

Thank you in advance.


This is best understood if you know something about the Frobenius endomorphism $F_p$, which sends $(x,y)$ to $(x^p, y^p)$ on the elliptic curve. Take any prime $\ell\neq p$. This endomorphism of the elliptic curve is also an endomorphism of the $2$-dimensional $\mathbb{F}_\ell$-vector space given by the points of order $\ell$ and the point at infinity (in fancy terms, the $\ell$-division points $E[\ell]$.). The characteristic polynomial of $F_p$ on $E[\ell]$ is $x^2-tx+p \mod\ell$. Note that $t=s_1$ becomes the trace of Frobenius ($\operatorname{Tr}(F_p)$) in this setting.

Similarly one defines $F_{p^n}$ by $(x,y)\mapsto (x^{p^n}, y^{p^n})$ and we have $\#E(\mathbb{F}_{p^n})=p^n+1-\operatorname{Tr}(F_{p^n})$ hence $s_n= \operatorname{Tr}(F_{p^n})$. Now note that

  1. The characteristic polynomial of $F_p$ is independent of $\ell$, so can be viewed as a polynomial in $\mathbb{Z}[x]$,
  2. $F_{p^n} = F_p^n$.

Calling $\alpha, \bar\alpha$ the roots in $\mathbb{C}$ of the characteristic polynomial of $F_p$ (i.e. its eigenvalues), we therefore have $s_n=\alpha^n+\bar\alpha^n$ by Point 2. This sequences satisfies the recurrence $$ s_0= 2,\quad s_1=t,\quad s_{n+1} -t s_n +p s_{n-1}=0 $$ as you can show by induction. So the $s_0=2$ comes from $\alpha^0+\bar\alpha^0$, but it took me a while to explain it from scratch.

  • 1
    $\begingroup$ Just a nitpick question. Aren't $E[l]$ $l$-torsion points as opposed to $l$-division points? I think I've usually heard $l$-division point to mean $P$ such that there exists $Q$, $[l]Q=P$. $\endgroup$ – DRF May 4 '15 at 14:49

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.