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

Question

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.

Answer 1

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.

Answer 2

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