# 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 $\mathbb{F}_{5^2}$, where $E(\mathbb{F}_{5^2}):y^2=x^3+10x+17$.

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

Finding $t$ is easy, and according to $s_0=2$, the order must be $36$ points. Nevertheless, when I found the points, I got only $26$ points including the Identity, which is the same number if I choose $s_0=1$.

What is the condition to determine $s_0$? Is it supposed to be $2$ at all cases? and Why? Worth to say, the method that I use to find the points for $E(\mathbb{F}_{p^2})$ is the same method to find them for elliptic curve over $\mathbb{F}_p$.

-
What is the definition of $t$? – Ted May 12 '12 at 3:33
Dear Ted, by Weil's Theorem, we can compute #E(F_p^n) if we know #E(F_p). t can be computed from the equation #E(F_p)=p+1-t. This is the same t that we can use to find #E(F_p^n) by using the relation that has been mentioned in John J. McGee's thesis. – megjoh May 12 '12 at 3:51
@megjoh, there was a typo in the formula. As explained in the answer by Fsica to your other question, we always have $s_0=2$, as $s_n=Tr(F^n)$ is the trace of a power of the Frobenius automorphism on the Tate module (or a suitable limit of $\ell^m$-torsion subgroups), so it is the sum of the $n$th powers of the eigenvalues of $F$. – Jyrki Lahtonen May 12 '12 at 17:35
@megjoh, sorry about doubting that you might have been computing modulo 25. I was mislead by the fact that you use the equation $y^2=x^3+10x+17$ instead of $y^2=x^3+2$ that is the same equation over $F_{25}$. It occurred to me only later that this may be a part of a larger set of exercises, where you study several reductions of the given curve defined over the integers. – Jyrki Lahtonen May 12 '12 at 17:44
@Jyrki, Do not worry, I did not blame you for thinking that I was confused with the two terms, I understand why you thought that way. thank you. – megjoh May 13 '12 at 0:51

Starting from $s_0=2$ and the easily computable data (thanks to Ted) $\#E(F_5)=6=5+1-t$ that tells us $t=s_1=0$, we get $s_2=ts_1-5s_0=-10$. Therefore the formula tells us that $\#E(F_{25})=5^2+1-(-10)=36.$

In order to clear any potential misunderstandings I will list all the 36 points. To that end we first need to construct the field $F_{25}$. I constructed it using the primitive polynomial $x^2+3x+3$, so I use $F_{25}=F_5[x]/\langle x^2+3x+3\rangle$. I will denote the coset $x+\langle x^2+3x+3\rangle$ by $\alpha$, so the arithmetic will follow from the rule $\alpha^2=2+2\alpha$.

Let us list the discrete logarithms (base $\alpha$) of the elements of $F_{25}^*$: $$\begin{array}{l|ll|ll|l} n&\alpha^n&&&n&\alpha^n\\ \hline 0&1&&&12&4\\ 1&\alpha&&&13&4\alpha\\ 2&2+2\alpha&&&14&3+3\alpha\\ 3&4+\alpha&&&15&1+4\alpha\\ 4&2+\alpha&&&16&3+4\alpha\\ 5&2+4\alpha&&&17&3+\alpha\\ 6&3&&&18&2\\ 7&3\alpha&&&19&2\alpha\\ 8&1+\alpha&&&20&4+4\alpha\\ 9&2+3\alpha&&&21&3+2\alpha\\ 10&1+3\alpha&&&22&4+2\alpha\\ 11&1+2\alpha&&&23&4+3\alpha\\ &&&&\infty&0 \end{array}$$ Now it becomes easy to list the points in $E(F_{25})$. As we are in characteristic five, we might as well use the equation $y^2=x^3+2$. For a given $x$ we have that $y^2=x^3+2$ has one solution, iff $x^3+2=0\Leftrightarrow \log (x^3+2)=\infty$; two solutions, iff $\log(x^3+2)$ is even; and no solutions, iff $\log(x^3+2)$ is odd. Furthermore, $\alpha^8$ is a primitive cubic root of unity, so $\log((\alpha^n)^3+2)$ is periodic with period 8. We get three full periods while $x$ runs over the elements of $F_{25}^*$.

Using the above table we see that when $\log x$ takes the respective values $0,1,2,3,4,5,6,7$, then $\log(x^3+2)$ takes the respective values $6,8,\infty,23,0,16,12,19$. There are 5 even values in the latter list and a single $\infty$, so in the range $0\le\log x<8$ we get 11 points on the curve. With $x$ ranging over all of $F_{25}^*$ we get thus $3\cdot11=33$ points. Add the point at infinity as well as the points $x=0$, $y=\pm\sqrt{2}=\pm(2+3\alpha)$, and we get altogether $$33+1+2=36\ \text{points}\ \in E(F_{25}).$$

For the sake of completeness I list the points. Let $\omega=\alpha^8=1+\alpha$ be a fixed primitive cubic root of unity. Then we have

• 6 points of the form $(\omega^j,\pm\alpha^3)$, $j=0,1,2$,
• 6 points of the form $(\omega^j\alpha,\pm\alpha^4)$, $j=0,1,2$,
• 3 points of the form $(\omega^j\alpha^2,0)$, $j=0,1,2$,
• 6 points of the form $(\omega^j\alpha^4,\pm1)$, $j=0,1,2$,
• 6 points of the form $(\omega^j\alpha^5,\pm\alpha^8)$, $j=0,1,2$,
• 6 points of the form $(3\omega^j,\pm2)$, $j=0,1,2$,
• 2 points $(0,\pm\alpha^9)$,
• and the point at infinity.

Remembering that $\alpha^k\in F_5$, iff $6\mid k$ allows us to identify the six points in $E(F_5)$ on this list.

-
As $E(F_5)$ is a subgroup of $E(F_{5^n})$ Lagrange's theorem tells us that $$6\mid\#E(F_{5^n})$$ for all $n$. – Jyrki Lahtonen May 12 '12 at 18:56
Thank you Jyrki. – megjoh May 13 '12 at 0:37
I had to try the method of inserting tables as described by Zev here. Sorry about the bump :-( – Jyrki Lahtonen May 18 '12 at 10:46
It was already Clear. – megjoh May 20 '12 at 23:10

You can use Sage to solve your problem. sage: E = EllipticCurve(GF($5^2$,'c'),[10,17]); Elliptic Curve defined by $y^2 = x^3 + 2$ over Finite Field in c of size $5^2$ and so: sage: E.order() 36

-

$E$ has 6 points over $\mathbb{F}_5$, so $t=0$. Then $S_1 = S_3 = 0$, so $\#E(\mathbb{F}_{5^2}) = 5^2 + 1 = 26$, as you counted.

Edit: Typo in the original post (it said $s_{n+1}$ instead of $s_n$). See Jyrki's Lahtonen answer for the correct calculation.

-
Thank you. If we forget the numbers for a moment. Still my main question was about s_0 in the relation that had been used by John J. McGee, In General, what is the condition on this initial value. But thanks anyway, I better rephrase my question above. – megjoh May 12 '12 at 11:57
The formula relates $\#E(\mathbb{F}_{p^n})$ to $s_{n+1}$, so for $\#E(\mathbb{F}_{5^2})$ we need the value of $s_3$, not $s_2$. – Ted May 12 '12 at 16:09
Never mind, that doesn't make sense, because for $n=1$ we ought to recover the original $p+1-t$. Something is wrong here... – Ted May 12 '12 at 16:11
In that case I'm fairly sure there is a typo in the formula. $s_1=t$ relates to $\#E(F_{5^1})$ after all. – Jyrki Lahtonen May 12 '12 at 16:11
Originally, your post said $s_{n+1}$ instead of $s_n$. – Ted May 13 '12 at 2:04