# Determine groups for elliptic curves over a finite field

I have the following question:

Determine all possible groups $$E(F_5)$$ for elliptic curves over $$F_5$$. What are their orders?

I am completely in the dark here about calculating the groups and their orders... I know how are the groups defined (how we calculate +, -...), I have Hasse's Theorem here somewhere, apparently an algorithm for calculating the order similar to "Baby Step, Giant Step" one, the Long-Trotter Method, Shank's Method, but I actually didn't know how to link them because I got no example in the course and I can not find anything on the internet.

Is calculating the number of elements giving me something about the group of the curve? I have listed all the possible curves regarding Weierstrass form and $$27*b^2 + 4*a^3 \neq 0$$, but I don't know how to proceed.

• You can list every product of two cyclic groups with at most $5^2+1$ elements, you can list every $y^2 = x^3+ax+b, 4a^3+27b^2 \ne 0$ equation and determinate $E(F_5)$. Do you mean a deeper method not needing such an enumeration and generalizable to every $p$ ? – reuns Jun 26 at 16:36
• By Hasse's theorem, the number of points is between $(\sqrt5\pm1)^2$. Also an elliptic curve group over a finite field is the direct product of two cyclic groups. – Lord Shark the Unknown Jun 26 at 17:04

Using sage in a simpler manner we obtain the following detailed information:

sage: F = GF(5)
sage: curves = []
sage: for a, b in cartesian_product([F, F]):
....:     try:
....:         curves.append(EllipticCurve(F, [a, b]))
....:     except:
....:         print "Singular curve for a=%s b=%s" % (a, b)
....:
Singular curve for a=0 b=0
Singular curve for a=2 b=2
Singular curve for a=2 b=3
Singular curve for a=3 b=1
Singular curve for a=3 b=4

sage: orders = list(set([ E.order() for E in curves ]))
sage: orders.sort()

sage: for ord in orders:
....:     print "ORDER", ord
....:     for E in curves:
....:         if E.order() != ord:    continue
....:         print '\t%s' % E
....:         print '\tGenerator(s):', ' AND '.join([ '%s of order %s' % (P.xy(), P.order()) for P in E.gens() ])
....:         print
....:
ORDER 2
Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 5
Generator(s): (0, 0) of order 2

ORDER 3
Elliptic Curve defined by y^2 = x^3 + 4*x + 2 over Finite Field of size 5
Generator(s): (3, 1) of order 3

Elliptic Curve defined by y^2 = x^3 + 4*x + 3 over Finite Field of size 5
Generator(s): (2, 2) of order 3

ORDER 4
Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 5
Generator(s): (3, 0) of order 2 AND (2, 0) of order 2

Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 5
Generator(s): (1, 2) of order 4

Elliptic Curve defined by y^2 = x^3 + x + 3 over Finite Field of size 5
Generator(s): (4, 1) of order 4

ORDER 5
Elliptic Curve defined by y^2 = x^3 + 3*x + 2 over Finite Field of size 5
Generator(s): (1, 1) of order 5

Elliptic Curve defined by y^2 = x^3 + 3*x + 3 over Finite Field of size 5
Generator(s): (3, 2) of order 5

ORDER 6
Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 5
Generator(s): (2, 3) of order 6

Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field of size 5
Generator(s): (4, 4) of order 6

Elliptic Curve defined by y^2 = x^3 + 3 over Finite Field of size 5
Generator(s): (1, 3) of order 6

Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 5
Generator(s): (3, 1) of order 6

ORDER 7
Elliptic Curve defined by y^2 = x^3 + 2*x + 1 over Finite Field of size 5
Generator(s): (0, 1) of order 7

Elliptic Curve defined by y^2 = x^3 + 2*x + 4 over Finite Field of size 5
Generator(s): (4, 1) of order 7

ORDER 8
Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 5
Generator(s): (2, 1) of order 4 AND (1, 0) of order 2

Elliptic Curve defined by y^2 = x^3 + 4*x + 1 over Finite Field of size 5
Generator(s): (0, 1) of order 8

Elliptic Curve defined by y^2 = x^3 + 4*x + 4 over Finite Field of size 5
Generator(s): (0, 2) of order 8

ORDER 9
Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 5
Generator(s): (4, 2) of order 9

Elliptic Curve defined by y^2 = x^3 + x + 4 over Finite Field of size 5
Generator(s): (2, 2) of order 9

ORDER 10
Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 5
Generator(s): (3, 1) of order 10

sage:

The Hasse bound insures a deviation of at most $$2\sqrt 5$$ for the number of $$F$$-rational points of an elliptic curve over $$F=\Bbb F_5$$, compared with the number of $$F$$-rational points ($$5+1=6$$) in the projective space $$\Bbb P^1$$ over $$F$$.

Possible values are thus $$2,3,4,5,6,7,8,9,10$$. All of them are taken for particular elliptic curves $$E$$.

In almost all cases we have a cyclic group $$E(F)$$ (and the generator has the order of the group of rational points of $$E$$ over $$F$$). In some special cases we have a $$\Bbb Z/2\times \Bbb Z/d$$ structure and two generators.