#!/usr/bin/env python
# coding: utf-8

# # 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:
# 
# - [The "getting started" tutorial](http://doc.sagemath.org/html/en/tutorial/index.html);
# - [Other SageMath tutorials](http://doc.sagemath.org/html/en/thematic_tutorials/index.html);
# - [Finite fields (reference)](http://doc.sagemath.org/html/en/reference/finite_rings/index.html);
# - [Number fields](http://doc.sagemath.org/html/en/constructions/number_fields.html), [reference](http://doc.sagemath.org/html/en/reference/number_fields/index.html);
# - [Quadratic forms (reference)](http://doc.sagemath.org/html/en/reference/quadratic_forms/index.html);
# - [Elliptic curves](http://doc.sagemath.org/html/en/constructions/elliptic_curves.html), [reference](http://doc.sagemath.org/html/en/reference/curves/index.html).
# 
# See also the book [Computational Mathematics with SageMath](http://dl.lateralis.org/public/sagebook/sagebook-ba6596d.pdf).
# 
# ## Finite fields

# We create finite fields by passing their cardinality

# In[1]:


Fp = GF(11)


# In[2]:


Fp


# In[3]:


Fq = GF(11^2)
Fq


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

# In[4]:


z = Fq.gen()
z


# In[5]:


z^120


# Same thing in one go

# In[6]:


K.<t> = GF(next_prime(2^128)^2)
K


# ## Elliptic curves

# Curves over $ℚ$

# In[7]:


E = EllipticCurve([-10,10])
E


# In[8]:


E.plot()


# Cuvers over other fields

# In[9]:


F = EllipticCurve(GF(11), [1, 0])
F


# In[10]:


F.order()


# In[11]:


F.cardinality()


# In[12]:


F.points()


# In[13]:


P = F.random_point()
P


# In[14]:


P.order()


# Isomorphisms

# In[15]:


F.automorphisms()


# In[16]:


aut = F.change_ring(GF(11^2)).automorphisms()
aut


# In[17]:


aut[3], aut[3]^2


# In[18]:


G = EllipticCurve(GF(11), [3, 0])
F.is_isomorphic(G)


# In[19]:


u = F.isomorphism_to(G)
u


# In[20]:


P, u(P)


# Group structure

# In[21]:


F.abelian_group()


# In[22]:


g = F.gens()[0]
g


# In[23]:


g.order()


# Construct an isogeny with given kernel

# In[24]:


origin = 6*g
origin


# In[25]:


F.point([0,0])


# In[26]:


I = F.isogeny(origin)
I


# In[27]:


I.rational_maps()


# In[28]:


FF = I.codomain()


# In[29]:


FF


# In[30]:


FF.abelian_group()


# In[31]:


FF.plot()


# The same example, over the rationals

# In[32]:


E = EllipticCurve([1,0])


# In[33]:


P = E.lift_x(0)
P


# In[34]:


P.order()


# In[35]:


J = E.isogeny(P)
EE = J.codomain()
EE


# 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


# ## Orders
# 
# The functionality is a bit limited, but still useful

# In[38]:


E = EllipticCurve([1,0])
E


# In[39]:


E.has_cm()


# In[40]:


E.cm_discriminant()


# Over finite fields

# In[41]:


E = EllipticCurve(GF(101), [1,2])
E


# In[42]:


E.j_invariant()


# In[43]:


chi = E.frobenius_polynomial()
chi


# In[44]:


chi.discriminant()


# In[45]:


E.trace_of_frobenius()


# In[46]:


O = E.frobenius_order()
O


# In[47]:


O.is_maximal()


# In[48]:


O.discriminant()


# In[49]:


K = O.number_field()
K


# In[50]:


OK = K.maximal_order()
OK


# In[51]:


OK.discriminant()


# In[52]:


K.class_number()


# In[53]:


K.class_group()


# In[54]:


O.class_number()


# In[55]:


H = hilbert_class_polynomial(-400)
H


# In[56]:


H.is_irreducible()


# In[57]:


H.change_ring(GF(101)).factor()


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