Cfrgtkky

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.

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.

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