Using elliptic curves and isogenies in SageMath

This is a short tutorial to get started with elliptic curves in SageMath. For a complete reference, see the official documentation:

See also the book Computational Mathematics with SageMath.

Finite fields

We create finite fields by passing their cardinality

In [1]:
Fp = GF(11)
In [2]:
Fp
Out[2]:
Finite Field of size 11
In [3]:
Fq = GF(11^2)
Fq
Out[3]:
Finite Field in z2 of size 11^2

For extension fields, the generator is obtained with the .gen() function.

In [4]:
z = Fq.gen()
z
Out[4]:
z2
In [5]:
z^120
Out[5]:
1

Same thing in one go

In [6]:
K.<t> = GF(next_prime(2^128)^2)
K
Out[6]:
Finite Field in t of size 340282366920938463463374607431768211507^2

Elliptic curves

Curves over $ℚ$

In [7]:
E = EllipticCurve([-10,10])
E
Out[7]:
Elliptic Curve defined by y^2 = x^3 - 10*x + 10 over Rational Field
In [8]:
E.plot()
Out[8]:

Cuvers over other fields

In [9]:
F = EllipticCurve(GF(11), [1, 0])
F
Out[9]:
Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 11
In [10]:
F.order()
Out[10]:
12
In [11]:
F.cardinality()
Out[11]:
12
In [12]:
F.points()
Out[12]:
[(0 : 0 : 1), (0 : 1 : 0), (5 : 3 : 1), (5 : 8 : 1), (7 : 3 : 1), (7 : 8 : 1), (8 : 5 : 1), (8 : 6 : 1), (9 : 1 : 1), (9 : 10 : 1), (10 : 3 : 1), (10 : 8 : 1)]
In [13]:
P = F.random_point()
P
Out[13]:
(5 : 3 : 1)
In [14]:
P.order()
Out[14]:
3

Isomorphisms

In [15]:
F.automorphisms()
Out[15]:
[Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 11
   Via:  (u,r,s,t) = (1, 0, 0, 0),
 Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 11
   Via:  (u,r,s,t) = (10, 0, 0, 0)]
In [16]:
aut = F.change_ring(GF(11^2)).automorphisms()
aut
Out[16]:
[Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 11^2
   Via:  (u,r,s,t) = (1, 0, 0, 0),
 Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 11^2
   Via:  (u,r,s,t) = (10, 0, 0, 0),
 Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 11^2
   Via:  (u,r,s,t) = (4*z2 + 3, 0, 0, 0),
 Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 11^2
   Via:  (u,r,s,t) = (7*z2 + 8, 0, 0, 0)]
In [17]:
aut[3], aut[3]^2
Out[17]:
(Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 11^2
   Via:  (u,r,s,t) = (7*z2 + 8, 0, 0, 0),
 Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 11^2
   Via:  (u,r,s,t) = (10, 0, 0, 0))
In [18]:
G = EllipticCurve(GF(11), [3, 0])
F.is_isomorphic(G)
Out[18]:
True
In [19]:
u = F.isomorphism_to(G)
u
Out[19]:
Generic morphism:
  From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 11
  To:   Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 11
  Via:  (u,r,s,t) = (8, 0, 0, 0)
In [20]:
P, u(P)
Out[20]:
((5 : 3 : 1), (3 : 6 : 1))

Group structure

In [21]:
F.abelian_group()
Out[21]:
Additive abelian group isomorphic to Z/12 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 11
In [22]:
g = F.gens()[0]
g
Out[22]:
(8 : 5 : 1)
In [23]:
g.order()
Out[23]:
12

Construct an isogeny with given kernel

In [24]:
origin = 6*g
origin
Out[24]:
(0 : 0 : 1)
In [25]:
F.point([0,0])
Out[25]:
(0 : 0 : 1)
In [26]:
I = F.isogeny(origin)
I
Out[26]:
Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 11 to Elliptic Curve defined by y^2 = x^3 + 7*x over Finite Field of size 11
In [27]:
I.rational_maps()
Out[27]:
((x^2 + 1)/x, (x^2*y - y)/x^2)
In [28]:
FF = I.codomain()
In [29]:
FF
Out[29]:
Elliptic Curve defined by y^2 = x^3 + 7*x over Finite Field of size 11
In [30]:
FF.abelian_group()
Out[30]:
Additive abelian group isomorphic to Z/6 + Z/2 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 7*x over Finite Field of size 11
In [31]:
FF.plot()
Out[31]:

The same example, over the rationals

In [32]:
E = EllipticCurve([1,0])
In [33]:
P = E.lift_x(0)
P
Out[33]:
(0 : 0 : 1)
In [34]:
P.order()
Out[34]:
2
In [35]:
J = E.isogeny(P)
EE = J.codomain()
EE
Out[35]:
Elliptic Curve defined by y^2 = x^3 - 4*x over Rational Field

In (very) limited cases, Sage can compute the isogeny given the image curve and the degree

In [36]:
JJ = E.isogeny(None, codomain=EE, degree=2)
In [37]:
J == JJ
Out[37]:
True

Orders

The functionality is a bit limited, but still useful

In [38]:
E = EllipticCurve([1,0])
E
Out[38]:
Elliptic Curve defined by y^2 = x^3 + x over Rational Field
In [39]:
E.has_cm()
Out[39]:
True
In [40]:
E.cm_discriminant()
Out[40]:
-4

Over finite fields

In [41]:
E = EllipticCurve(GF(101), [1,2])
E
Out[41]:
Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 101
In [42]:
E.j_invariant()
Out[42]:
4
In [43]:
chi = E.frobenius_polynomial()
chi
Out[43]:
x^2 - 2*x + 101
In [44]:
chi.discriminant()
Out[44]:
-400
In [45]:
E.trace_of_frobenius()
Out[45]:
2
In [46]:
O = E.frobenius_order()
O
Out[46]:
Order in Number Field in phi with defining polynomial x^2 - 2*x + 101
In [47]:
O.is_maximal()
Out[47]:
False
In [48]:
O.discriminant()
Out[48]:
-400
In [49]:
K = O.number_field()
K
Out[49]:
Number Field in phi with defining polynomial x^2 - 2*x + 101
In [50]:
OK = K.maximal_order()
OK
Out[50]:
Gaussian Integers in Number Field in phi with defining polynomial x^2 - 2*x + 101
In [51]:
OK.discriminant()
Out[51]:
-4
In [52]:
K.class_number()
Out[52]:
1
In [53]:
K.class_group()
Out[53]:
Class group of order 1 of Number Field in phi with defining polynomial x^2 - 2*x + 101
In [54]:
O.class_number()
Out[54]:
4
In [55]:
H = hilbert_class_polynomial(-400)
H
Out[55]:
x^4 - 1938773508354872717845384224*x^3 + 12869286863161864184636279443710336*x^2 - 19075061455767889406477974994607212544*x + 87448873738295790450948276123544550117376
In [56]:
H.is_irreducible()
Out[56]:
True
In [57]:
H.change_ring(GF(101)).factor()
Out[57]:
(x + 7) * (x + 24) * (x + 64) * (x + 97)

Exercises

Give the list of all elliptic curves with complex multiplication over $ℚ$

In [ ]:
 

Give the list of all supsersingular elliptic curves over $𝔽_{101^2}$

In [ ]:
 

Find a prime $p$ and an elliptic curve $E/𝔽_p$ such that $\#E(𝔽_p) = 101$.

Hint: try to find a solution to $p+1-t = 101$, then compute the discriminant of the Frobenius and use complex multiplication theory.

In [ ]:
 

Use the previously found curve to construct an isogeny of degree $101^{10}$

In [ ]:
 

Find a prime $p$ and an elliptic curve $E/𝔽_p$ such that $\#E(𝔽_p) = 2^{127} - 1$

Warning: this is obviously a difficult exercise, and requires knowledge not contained in the course (for example, of Cornacchia's algorithm)

In [ ]: