Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
Thank You FSica. –  megjoh May 12 '12 at 15:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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