Sfrgttk

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=-1pm isqrt2$.

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-2operatorname{Re}(-1+isqrt2)^k.
$$

For example, when $k=2$, $alpha^2=(-1+isqrt2)^2=-1-2isqrt2$
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.