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

# # Using elliptic curves and isogenies in Sage
# 
# ## 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()


# Group structure

# In[15]:


F.abelian_group()


# In[16]:


g = F.gens()[0]
g


# In[17]:


g.order()


# Construct an isogeny with given kernel

# In[18]:


origin = 6*g
origin


# In[19]:


F.point([0,0])


# In[20]:


I = F.isogeny(origin)
I


# In[21]:


I.rational_maps()


# In[22]:


FF = I.codomain()


# In[23]:


FF


# In[24]:


FF.abelian_group()


# In[25]:


FF.plot()


# The same example, over the rationals

# In[26]:


E = EllipticCurve([1,0])


# In[27]:


P = E.lift_x(0)
P


# In[28]:


P.order()


# In[29]:


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


JJ = E.isogeny(None, codomain=EE, degree=2)


# In[31]:


J == JJ


# ## Your turn: exercices!
# 
# ### Diffie-Hellman 
# 
# Implement the (naive) Diffie-Helman key exchange scheme with elliptic curves.
# 
# #### 1. Find a curve of prime order
# 
# Choose a prime $p$. Take curves at random over $𝔽_p$ until you find one with prime order.
# 
# **Suggestion:** For a start, take $p$ of ~60 bits. When your code works well enough you can try 160 bits (it may take a few minutes to find a curve)

# In[ ]:





# #### 2. Implement the scheme
# 
# Write a function to sample secret keys, and a function to produce public keys. Perform the key exchnage and verify that Alice and Bob obtain the same key.

# In[ ]:





# ### ECM Factoring method
# 
# Implement Lenstra's factoring method. See the [lecture notes](https://arxiv.org/pdf/1711.04062.pdf), Section 5.
# 
# **Note:** Sage has limited support for curves over $ℤ/Nℤ$, just enough to implement ECM.

# In[ ]:





# ### Generating irreducible polynomials
# 
# Implement the Couveignes-Lercier method for generating irreducible polynomials. See the [lecture notes](https://arxiv.org/pdf/1711.04062.pdf), Section 8.
# 
# **Note:** Sage has limited support for curves over $ℤ/Nℤ$, just enough to implement ECM.

# In[ ]: