# 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 [ ]: