How to find the order of elliptic curve over finite field extension? 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.
 A: 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 


*

*The characteristic polynomial of $F_p$ is independent of $\ell$, so can be viewed as a polynomial in $\mathbb{Z}[x]$,

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