UPDATE: 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$.

-

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.
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$. – DRF May 4 '15 at 14:49