1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$ ? $\endgroup$ – reuns Jun 26 at 16:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Lord Shark the Unknown Jun 26 at 17:04
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.