3
$\begingroup$

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.

  • 0
    @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.2012-05-13

3 Answers 3

4

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.

  • 0
    It was already Clear.2012-05-20
3

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

0

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

  • 0
    oh yes, thank you Ted. Sorry for that.2012-05-13