Cardinality of elliptic curve using Hasse bound

Question

Unfortunately, we do not get solutions for exercises, thus I would like to check the validity of my argumentation.

Given the elliptic curve E: $y^2 = x^3 + x + 1$ mod 11, calculate the order of the elliptic curve using the Hasse bound.

By assumption, we know that there is a point P on E of order 7. Now using the Hasse bound, one gets that: $6 \leq |E(\mathbb{F}_{11})| \leq 18$. If we use now that there are $d_1, d_2$ s.t. $d_1 | d_2$ and $E(\mathbb{F}_{11}) \cong \mathbb{Z}_{d_1} \times \mathbb{Z}_{d_2}$. I get the possibilities of following $(d_1,d_2)$ pairs: (1,7), (2,7), (1,14). But since 0 is no quadratic residue mod 11, every valid x coordinate implies two finite points on E, i.e. the cardinality of E is odd. Thus, $|E(\mathbb{F}_{11})| = 7$.

I appreciate any feedback!

Answer 1

The Hasse bound with given element with order $7$ indicates that one have either order 7 or 14. 14 means we have an element of order 2, i.e. $P + P = \mathcal{O}$ that is $P = - P$ and this implies $P.y = 0$.

To see the existence of such an element, we need to find the roots to $ f(x) = x^3 + x + 1 \bmod 11$. $x =2$ is the only root of $f(x)$ ^* therefore $P=(2,0)$ is on this curve. As a result we have order 14 not 7.

---

SageMath code to verify;

p = 11
a = 1
b = 1

K = GF(p)
E = EllipticCurve(K,[a,b])
print(E)
print("cardinality = ", E.cardinality())


for P in E:
    print(P, P.order())
    
E.plot()

and output

Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 11
cardinality =  14
(0 : 1 : 0) 1
(0 : 1 : 1) 7
(0 : 10 : 1) 7
(1 : 5 : 1) 14
(1 : 6 : 1) 14
(2 : 0 : 1) 2
(3 : 3 : 1) 7
(3 : 8 : 1) 7
(4 : 5 : 1) 14
(4 : 6 : 1) 14
(6 : 5 : 1) 7
(6 : 6 : 1) 7
(8 : 2 : 1) 14
(8 : 9 : 1) 14

---

^* One can try to factor, try all values, or use SageMath

x = PolynomialRing(GF(11), 'x').gen()
f = x^3 +x + 1
f.roots()

That outputs [(2, 1)] indicating 2 is the only root with multiplicity 1.