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

Thank you in advance.

  • $\begingroup$ What is the definition of $t$? $\endgroup$ – Ted May 12 '12 at 3:33
  • $\begingroup$ 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. $\endgroup$ – megjoh May 12 '12 at 3:51
  • 1
    $\begingroup$ @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$. $\endgroup$ – Jyrki Lahtonen May 12 '12 at 17:35
  • $\begingroup$ @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. $\endgroup$ – Jyrki Lahtonen May 12 '12 at 17:44
  • $\begingroup$ @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. $\endgroup$ – 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.

  • 1
    $\begingroup$ 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$. $\endgroup$ – Jyrki Lahtonen May 12 '12 at 18:56
  • $\begingroup$ I had to try the method of inserting tables as described by Zev here. Sorry about the bump :-( $\endgroup$ – Jyrki Lahtonen May 18 '12 at 10:46
  • $\begingroup$ It was already Clear. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – megjoh May 12 '12 at 11:57
  • $\begingroup$ 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$. $\endgroup$ – Ted May 12 '12 at 16:09
  • $\begingroup$ Never mind, that doesn't make sense, because for $n=1$ we ought to recover the original $p+1-t$. Something is wrong here... $\endgroup$ – Ted May 12 '12 at 16:11
  • 2
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen May 12 '12 at 16:11
  • 2
    $\begingroup$ Originally, your post said $s_{n+1}$ instead of $s_n$. $\endgroup$ – Ted May 13 '12 at 2:04

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.