# Cardinality of elliptic curve using Hasse bound

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!

• Note: We can already deduce from $ord(7)$ and Lagrange that $|E(\mathbb{Z}_{11})| \in \{7,14\}$. Jun 18, 2022 at 21:22

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.

• Thanks a lot! I understand now how it follows. Jun 18, 2022 at 23:29