# elliptic curve $~y^2 = x^3 + 3x +8~ (mod~ 13)~$ - torsion groups

Corollary $$6.4.$$ Let $$E$$ be an elliptic curve and let $$m \in \mathbb{Z}$$ with $$m \neq 0$$.

$$(b)$$ If $$m \neq 0$$ in $$K$$, i.e., if either $$\operatorname{char}(K) = 0$$ or $$p := \operatorname{char}(K) > 0$$ and $$p \nmid m$$, then $$E[m] = \mathbb{Z}/m \mathbb{Z} \times \mathbb{Z}/m \mathbb{Z}$$.

(page $$86$$ of [Silverman, The Arithmetic of Elliptic Curves, $$2^{nd}$$ Edition])

Let $$E: y^2 = x^3 + 3x + 8$$ over $$\mathbb{Z}/13 \mathbb{Z}$$. I just calculated the points on this curve. There are $$\#E[3] \stackrel{?}{=} 2$$ points of order $$3$$ and $$\#E[9] \stackrel{?}{=} 6$$ points of order $$~9~$$.

$$(i)~~$$ I expected $$9$$ points of order $$3$$, since $$\#E[3] = \#\left(\mathbb{Z}/3 \mathbb{Z} \times \mathbb{Z}/3 \mathbb{Z}\right) = 9$$. Why are there just $$2$$ points of order $$3$$?

$$(ii) ~~$$ I calculated $$\#E(\mathbb{Z}/13 \mathbb{Z}) = 9$$ (by bruteforce). As far as I understand the above Corollary 6.4, there should be some points of order $$5$$, since $$p = 13 \nmid 5$$. But the existence of such a point $$P \in E[5]$$ would imply the existence of some subgroup $$\langle P \rangle \leq E(\mathbb{Z}/13 \mathbb{Z})$$ with order $$5$$ as-well. This can't happen, since the order of a subgroup must divide the order of the upper group. Since $$5 \nmid 9$$, there can't be any points of order $$5$$.

What am I missing?

• For (ii), that Corollary in Silverman is referring to the structure of the $m$-torsion points over $\overline{K}$. Jul 14, 2019 at 6:37
• How did you calculate those points? Jul 14, 2019 at 6:46
• Are you sure the $9$-torsion isn't cyclic? Jul 14, 2019 at 6:55
• The theorem you cite is only valid when $K$ is algebraically closed. Jul 14, 2019 at 6:57
• @BrandonCarter : thanks a lot, i see my mistake now Jul 14, 2019 at 7:29

This is a computer assisted answer that shows explicitly the corresponding field extensions of $$\Bbb F_{13}$$ that contain all $$3$$-torsion, respectively all $$9$$-torsion points. (A comment would not fit with all delivered information.)

Sometimes it is good to be able to verify and construct explicitly objects in the framework of a given elliptic curve.

Things are already clear from the comments, but sometimes computer brute force clears by example alternatively or complementarily. If explicit, structural computations using sage are not wanted, please ignore this answer.

We initialize the curve $$E$$ over the field with $$p=13$$ elements, ask for its order, generator(s), and points.

sage: E = EllipticCurve( GF(13), [3, 8] )
sage: E
Elliptic Curve defined by y^2 = x^3 + 3*x + 8 over Finite Field of size 13
sage: E.order().factor()
3^2
sage: for P in E.points():
....:     print "Point %8s of order %s" % (P.xy() if P != E(0) else 'ZERO', P.order())
....:
Point     ZERO of order 1
Point   (1, 5) of order 9
Point   (1, 8) of order 9
Point   (2, 3) of order 9
Point  (2, 10) of order 9
Point   (9, 6) of order 3
Point   (9, 7) of order 3
Point  (12, 2) of order 9
Point (12, 11) of order 9
sage: E.gens()
((12 : 11 : 1),)
sage: G = E.gens()[0]    # the generator
sage: G.order()
9


We have all nine $$\Bbb F_{13}$$-rational points on $$E$$, a generator is the point $$G= (-1,11)$$ above.

Let us compute a suitable field extension of $$\Bbb F_{13}$$ that contains all $$\bar{\Bbb F}_{13}$$-three-torsion points. Sage computes for us the corresponding division polinomial (for the $$x$$-coordinate of a point $$(x,y)$$ on $$E$$). This polynomial is:

sage: E.division_polynomial(3).factor()
(3) * (x + 4) * (x^3 + 9*x^2 + 9*x + 9)


One root, $$-4$$, of this polynomial already lives over $$\Bbb F_{13}$$, it is the common $$x$$-component of the two points of order three listed above, $$(9,\pm6)$$. To have them all, the needed extension is...

sage: F.<a> = GF( 13^3, modulus = x^3 + 9*x^2 + 9*x + 9 )
sage: F
Finite Field in a of size 13^3
sage: F.modulus()
x^3 + 9*x^2 + 9*x + 9
sage: a.minpoly()
x^3 + 9*x^2 + 9*x + 9
sage: # we consider the base change of E from GF(13) to F = GF(13^3)
sage: EF = E.base_extend(F)
sage: EF
Elliptic Curve defined by y^2 = x^3 + 3*x + 8 over Finite Field in a of size 13^3
sage: EF.base_field()
Finite Field in a of size 13^3
sage: EF.base_field() == F
True


We let now sage compute the number of $$F$$-rational points, $$F=\Bbb F_{13}(a)\cong \Bbb F_{13^4}$$:

sage: EF.order().factor()
2^2 * 3^4 * 7


And the three-torsion points of order $$3$$ over $$F$$ are:

sage: for P in EF.points():
....:     if P.order() == 3:
....:         print P
....:
(9 : 6 : 1)
(9 : 7 : 1)
(a : 2*a + 5 : 1)
(a : 11*a + 8 : 1)
(4*a^2 + 3*a : 5*a^2 + 7*a + 8 : 1)
(4*a^2 + 3*a : 8*a^2 + 6*a + 5 : 1)
(9*a^2 + 9*a + 4 : 5*a^2 + 5*a : 1)
(9*a^2 + 9*a + 4 : 8*a^2 + 8*a : 1)
sage:


As expected, there are two points with $$a$$ as the first coordinate.

The polynomial needed for the $$9$$-division has the following factors:

sage: for f, multiplicity in E.division_polynomial(9).factor():
....:     print f
....:
x + 1
x + 4
x + 11
x + 12
x^3 + 4*x^2 + 8*x + 7
x^3 + 8*x^2 + x + 6
x^3 + 9*x^2 + 9*x + 9
x^9 + 2*x^7 + 5*x^6 + 11*x^5 + x^4 + 12*x^3 + 11*x^2 + 7*x + 9
x^9 + 6*x^8 + 7*x^7 + x^6 + x^5 + 10*x^4 + 9*x^3 + 2*x^2 + 7*x + 7
x^9 + 10*x^8 + 6*x^7 + 7*x^6 + 3*x^5 + 3*x^4 + 7*x^3 + 9*x^2 + 7*x + 10


Again, the linear factors correspond to the points in $$(x,y)\in E(\Bbb F_{13})$$ with first component $$x\in\{-4,-11,-12\}=\{11,2,1\}$$.

To have all $$9$$-division points, we need a field containing the roots of all above factors. There is exactly one field $$L$$ with $$\Bbb F_{13^9}$$ elements up to isomorphism, which can be constructed from the polynomial ring $$\Bbb F_{13}[b]$$ by going modulo one of the above polynomials of degree nine, taken in x = $$b$$.

Of course, we can no longer compute all points in $$E(L)$$, then their order, then restrict to those of order exactly nine, but we can construct them starting from the roots of the division polynomial.

For instance, for the polynomial defining $$b$$ (as a root) of degree nine we have the nine conjugates, giving rise to $$18$$ points of order $$9$$ on $$E(L)$$, we show only nine of them, using only one choice for the square root, as provided by sage, the other one differs by sign:

sage: EL = E.base_extend(L)
sage: for bb in b.minpoly().roots(ring=L, multiplicities=False):
....:     ybb = sqrt( bb^3 + 3*bb + 8 )
....:     P = EL.point( (bb, ybb) )
....:     print "Order %s for point with components:\n%s\n%s\n" % (P.order(), P.xy()[0], P.xy()[1])
....:
Order 9 for point with components:
b
11*b^8 + 7*b^7 + 5*b^6 + 2*b^4 + 10*b^3 + 7*b^2 + 6*b + 11

Order 9 for point with components:
3*b^8 + 4*b^7 + 4*b^6 + 3*b^5 + b^4 + 9*b^3 + 9*b
8*b^8 + 12*b^7 + 5*b^6 + 11*b^5 + 9*b^4 + 2*b^3 + 2*b^2 + 12*b + 12

Order 9 for point with components:
11*b^8 + 5*b^7 + 7*b^6 + 2*b^5 + 7*b^4 + 7*b^2 + b + 12
2*b^8 + 6*b^7 + 2*b^6 + 7*b^5 + 5*b^4 + 6*b^3 + 5*b^2 + 11

Order 9 for point with components:
4*b^8 + 9*b^7 + 4*b^5 + b^4 + 6*b^3 + b^2 + 11
b^8 + b^7 + 5*b^6 + b^5 + 12*b^4 + 2*b^2 + 5*b + 7

Order 9 for point with components:
6*b^8 + 10*b^7 + 3*b^6 + 8*b^5 + 2*b^4 + 10*b^3 + 3*b + 11
10*b^8 + 5*b^7 + 3*b^6 + 3*b^5 + 3*b^4 + 7*b^3 + b^2 + 7*b + 11

Order 9 for point with components:
5*b^8 + 6*b^7 + b^6 + 6*b^5 + 8*b^4 + 2*b^2 + 9*b + 10
7*b^8 + 3*b^7 + 6*b^6 + b^5 + 11*b^4 + 9*b^3 + 2*b^2 + 5*b + 4

Order 9 for point with components:
8*b^8 + 10*b^7 + 5*b^5 + 6*b^3 + 12*b^2 + b + 9
2*b^7 + 2*b^6 + 3*b^5 + 5*b^4 + 12*b^3 + 10*b^2 + 6*b + 5

Order 9 for point with components:
6*b^8 + b^7 + 7*b^6 + 3*b^5 + 6*b^4 + 2*b^3 + 10*b + 6
11*b^8 + 9*b^7 + 4*b^6 + 4*b^5 + 12*b^4 + 5*b + 10

Order 9 for point with components:
9*b^8 + 7*b^7 + 4*b^6 + 8*b^5 + b^4 + 6*b^3 + 4*b^2 + 5*b + 6
2*b^8 + 5*b^7 + b^6 + 5*b^5 + 7*b^4 + 6*b^3 + 4*b + 5

sage: