order of an elliptic curve

Question

I have found that the curve given by $x^3+x+1=y^2$ over $\mathbb{F_5}$ has 9 points. Now I am supposed to find the number of points of the same curve on $\mathbb{F}_{125}$. Using Hasse and the fact that 9 has to divide this order I have 5 possibilities: $108,117,126,135,144$ but here I don't know how to proceed.

Answer 1

The theory of $L$- and $\zeta$-functions gives the following result (tributed to some combination of Hasse, Weil and Davenport). The number of points on an elliptic curve defined over $\Bbb{F}_q$ can be written in the form $$ |E(\Bbb{F}_q)|=q+1-\omega_1-\omega_2, $$ where the complex numbers $\omega_1,\omega_2$ are conjugates of each other, and satisfy $\omega_1\omega_2=q$. Furthermore, for all positive integers $n$ we then have $$ |E(\Bbb{F}_{q^n})|=q^n+1-\omega_1^n-\omega_2^n. $$

In your case we have $\omega_1+\omega_2=-3$, and $\omega_1\omega_2=5$. Therefore $$ \omega_{1,2}=\frac{-3\pm\sqrt{9-20}}2=\frac{-3\pm i\sqrt{11}}2. $$

The Hasse-Weil-Davenport formula then gives $$ |E(\Bbb{F}_{125})|=125+1-\omega_1^3-\omega_2^3=108. $$

Basically knowing $|E(\Bbb{F}_q)|$ fully determines the Hasse - Weil zeta function of $E$. Then the Hasse - Davenport relations govern the way it changes under extensions of fields of constants.

Answer 2

I've been sleeping with Silverman and Tate's Rational Points on Elliptic Curves under my pillow for years now, with no effect. So here's the simple country coder's approach. (Spoiler: yes, 108 points.)

To construct the field $\mathbb{F}_{125}$ we need a cubic irreducible over $\mathbb{F}_5$. As irreducibility for a cubic amounts merely to the absence of linear factors, and especially as the problem statement already includes $p(X) = X^3+X+1$, we begin by verifying its irreducibility "mod 5":

irreduciblePoly :-
    for(X,0,4,1),
    0 is (1 + X*(1+X*X)) mod 5,
    !,
    fail.
irreduciblePoly.

This is a Prolog predicate that succeeds if there are no roots (linear factors) modulo 5. It uses a generator for/4 of integers specific to Amzi! Prolog, but SWI-Prolog has a similar built-in between/3 and GNU-Prolog provides both between/3 and for/3.

Since this polynomial passes muster, we implement the field operations plus/3 and times/3 in terms of quadratic polynomials that are reductions modulo $p(X)$ and 5. The addition of field elements is just adding like-coefficients:

plus(fElt(A0,A1,A2),fElt(B0,B1,B2),fElt(C0,C1,C2)) :-
    C0 is (A0+B0) mod 5,
    C1 is (A1+B1) mod 5,
    C2 is (A2+B2) mod 5.

Multiplication is fancier, but easily derived from $X^3=-X-1$ and $X^4 = -X^2-X$:

times(fElt(A0,A1,A2),fElt(B0,B1,B2),fElt(C0,C1,C2)) :-
    C0 is (A0*B0 - A2*B1 - A1*B2) mod 5,
    C1 is (A1*B0 + A0*B1 - A2*B1 - A1*B2 - A2*B2) mod 5,
    C2 is (A2*B0 + A1*B1 + A0*B2 - A2*B2) mod 5.

Pinning a note to my sleeve to remember to count the "point at infinity", the plan is to check all the values of $p(X)$ over $\mathbb{F}_{125}$ which are zero (one point on the curve) or which are (nonzero) quadratic residues (two points on the curve):

points(125,P,P) :- !.
points(N,P,R) :-
    intoField(N,FElt),
    evalPoly(FElt,Poly),
    increase(Poly,P,Q),
    On is N+1,
    points(On,Q,R).  /* last call */

so that we can run the query ?- points(0,1,Pts). (The 1 is the point at infinity!)

Here intoField/2 handily maps integers $0\leq N \leq 124$ into 125 field elements:

intoField(N,fElt(A0,A1,A2)) :-
    A0 is N mod 5,
    A1 is (N // 5) mod 5,
    A2 is (N // 25).

so that we can evaluate the polynomial for each of them:

evalPoly(FElt,Poly) :-
    times(FElt,FElt,FSqr),
    plus(fElt(1,0,0),FSqr,Pm),
    times(FElt,Pm,Pn),
    plus(fElt(1,0,0),Pn,Poly).

and adjust the point count accordingly:

increase(fElt(0,0,0),P,Q) :- !, Q is P+1.
increase(Poly,P,Q) :-
    quadResidue(Poly),
    !,
    Q is P+2.
increase(_,P,P).

I pre-built a "lookup" of quadratic residues quadResidue/2 by squaring each field element and assert'ing it (a Prolog mechanism to create facts dynamically), if not already there:

assertQuadraticResidues :-
    for(N,1,124,1),
    intoField(N,FElt),
    times(FElt,FElt,QRes),
    (   quadResidue(QRes)
     -> true
     ;  assert(quadResidue(QRes))
    ),
    fail.
assertQuadraticResidues.

Now we can run the code interpretively:

?- assertQuadraticResidues.

yes
?- points(0,1,Pts).

Pts = 108 

yes

confirming the Answer most elegantly obtained by Jyrki.