# Calculate the number of points of an elliptic curve in medium Weierstrass form over finite field

Let $$E$$ be the elliptic curve over $$\mathbb{F}_3$$ in medium Weierstrass form $$E:y^2=x^3+x^2+x+1$$. How to compute the number of points $$|E(\mathbb{F}_{3^k})|$$? I read that there are some formulas for computing number of points for short Weierstrass form by Frobenius endomorphism. But they don't work in this case.

Let $$\phi^k(x,y)= (x^{3^k},y^{3^k})$$ then $$\#E(\mathbb{F}_{3^k}) =\deg_s(\phi^k-1)$$. Is the endomorphism $$\phi^k-1$$ separable ? Yes because inserapable endomorphisms are of the form $$\rho \circ \phi$$. Then $$\deg_s(\phi^k-1) = \deg(\phi^k-1)=((\phi^*)^k-1)(\phi^k-1)\\= (\phi^*\phi)^k+1-(\phi^*)^k-\phi^k = 3^k+1-\alpha^k-(\alpha^*)^k$$ where $$\phi^*$$ is the dual isogeny such that $$\phi^* \phi = \deg(\phi) = 3$$ and $$\phi+\phi^* = t = 3+1-\#E(\mathbb{F}_{3})$$ and $$\alpha$$ is the root of the minimal polynomial $$X^2-t X + 3 = 0$$ of the Frobenius

magma code

     F := FiniteField(3); A<x,y> := AffineSpace(F,2);
C := Curve(A,y^2-x^3-x^2-x-1);
t :=3+1- #Points(ProjectiveClosure(C));
P<z> := PolynomialRing(Integers()); K<a> := NumberField(z^2-t*z+3); aa := Norm(a)/a;

for k in [2..10] do
Ck := BaseChange(C,FiniteField(3^k));
Ek := #Points(ProjectiveClosure(Ck));
[Ek,3^k+1-a^k-aa^k];
end for;


To obtain the minimal polynomial of endomorphisms :

Write that $$E(\overline{\mathbb{F}_3})$$ is a subgroup of $$\mathbb{Q}/\mathbb{Z}\times \mathbb{Q}/\mathbb{Z}$$ so any group homomorphism acts as a matrix $$A=\pmatrix{a & b \\c & d} \in M_2(\widehat{\mathbb{Z}})$$ (matrix of profinite integers). Then the dual homomorphism is $$A^*=\pmatrix{d & -b \\-c & a}$$ so that $$A^* A = \pmatrix{ad-bc& 0 \\ 0 & ad-bc}$$ and $$A + A^* = \pmatrix{a+d & 0 \\0 & a+d}$$, so they both act as direct multiplication by an element in $$\widehat{\mathbb{Z}}$$. If $$A$$ is an endomorphism (defined by polynomial equations) then so are $$A^*,A + A^*,A^*A$$ so the latter must act as multiplication by elements in $$\mathbb{Z}$$.

This is, indeed, easy after you have calculated the number of points over the prime field. It is straightforward to list them $$E(\Bbb{F}_3)=\{(0,1),(0,-1),(1,1),(1,-1),(-1,0),\infty\}.$$ In other words $$|E(\Bbb{F}_3)|=6.$$ This piece of information gives us the complex numbers $$\alpha,\overline{\alpha}$$ (see reuns's post for their interpretation as eigenvalues of Frobenius on the Tate module) as they are known to safisfy the equations $$|\alpha|^2=3$$ and $$\alpha+\overline{\alpha}=3+1-|E(\Bbb{F}_3)|=-2.$$ The real part of $$\alpha$$ is thus equal to $$-1$$, so $$\alpha=-1\pm i\sqrt2$$.

The formula for the number of rational poinst on the extension field then reads $$|E(\Bbb{F}_{3^k})|=3^k+1-\alpha^k-\overline{\alpha}^k=3^k+1-2\operatorname{Re}(-1+i\sqrt2)^k.$$

For example, when $$k=2$$, $$\alpha^2=(-1+i\sqrt2)^2=-1-2i\sqrt2$$ implying that $$|E(\Bbb{F}_9)|=9+1+2=12$$. This passes the litmus test of being divisible by $$|E(\Bbb{F}_3)|$$ (Lagrange's theorem from elementary group theory), possibly adding to our confidence in the correctness of the result.

• Can you list the point for $E(\mathbb{F}_9)$ as well? I'm confused how to do that because I got 14 points instead of 12.
– Nick
Commented Feb 28, 2019 at 9:30
• Let $i$ be a square root of $-1$ in $\Bbb{F}_9$. When $x=\pm i$ we get $y=0$ as the only choice of $y$. When $x=1\pm i$ we get two choices for $y$. When $x=-\pm i$ then it seems to me that $x^3+x^2+x+1$ is a non-square, so there are no points with such $x$. Commented Feb 28, 2019 at 9:56
• Anyway, that seems to be six points in $E(\Bbb{F}_9)\setminus E(\Bbb{F}_3)$. Commented Feb 28, 2019 at 9:57
• By the way, does this work for any form of elliptic curve? Sometimes I'm not sure because many results are discussed in short Weierstrass form and the cases for characteristics 2 and 3 are separated.
– Nick
Commented Feb 28, 2019 at 11:22
• @Nicky In characteristics 2 and 3 short Weierstrass form does not exist. But this applies to the (not-so-short) Weierstrass form anyway. Commented Feb 28, 2019 at 13:00