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

# # Welcome to Jupyter
# 
# This is just a **plain Python 2** notebook, no SageMath whatsoever!
# 
# To know what kernel you are running, look in the menu bar at the top right corner.
# 
# **Windows users:** to open a Jupyter notebook in the SageMath virtual appliance, do the following:
# 
# - Hit the `Right Ctrl + F1` keys,
# - Login with username `sage` and password `sage`
# - Type the following command:
# 
#   ~~~
#   BROWSER=chromium-browser DISPLAY=:0 sage --notebook ipython
#   ~~~
# - Hit the `Right Ctrl + F7` keys,
# - Start a new *Python 2* notebook (or start a *Sage* notebook directly if you want to skip the next 4 cells).

# In[1]:


1+1


# In[2]:


20/3


# In[3]:


20.0 / 3 


# In[4]:


type(20.0 / 3)


# ## Let's load the SageMath kernel
# 
# In the menu, select **Kernel → Change kernel → Sage 6.x**.
# 
# Alternatively, you can run the following *magic command* to use SageMath inside a python kernel.

# In[5]:


get_ipython().run_line_magic('load_ext', 'sage')


# In[6]:


1+1


# In[7]:


20/3


# In[8]:


type(20.0 / 3)


# ## Algebraic structures

# In[9]:


ZZ, QQ, RR, CC


# In[10]:


Zmod(30)


# In[11]:


GF(31)


# ### Most algebraic structures are organised as parent/elements

# In[12]:


GF(17).list()


# In[13]:


a = 2


# In[14]:


a.parent()


# In[15]:


ZZ is a.parent()


# In[16]:


a.is_unit()


# ### Conversions

# In[17]:


b = QQ(a)


# In[18]:


b == a


# In[19]:


b.parent()


# In[20]:


b.is_unit()


# 
# ## Working with notebooks
# 
# Notebooks are not referentially transparent

# In[21]:


a, b = 2, 3


# In[22]:


c = a + b


# In[23]:


c


# ### Exploring objects

# Completion

# In[24]:


ZZ.<tab>


# Documentation

# In[ ]:


get_ipython().run_line_magic('pinfo', 'ZZ.cardinality')


# Source code

# In[ ]:


get_ipython().run_line_magic('pinfo2', 'ZZ.cardinality')


# ## Polynomial rings
# 
# Sage has a special name `x` used for symbolic calculus

# In[25]:


a = x^2 - 1
a


# In[26]:


b = (x-1)*(x+1)
b


# In[27]:


a == b


# In[28]:


bool(a == b)


# ### `x` is just a variable name

# In[29]:


x = 2


# In[30]:


x^2 - 1


# In[31]:


x = SR.var('x')
a = x^2 - 1
a


# In[32]:


a(x=3)


# In[33]:


a - b


# In[34]:


(a-b).expand()


# In[35]:


x.parent()


# ### Forget about `x`!
# 
# We don't need symbolic calculus, we need **polynomials**

# In[36]:


QQ['x']


# In[37]:


R.<x> = QQ[]
R


# In[38]:


a = x^2 - 1
a


# In[39]:


a.parent()


# In[40]:


b = (x-1)*(x+1)
b


# In[41]:


a == b


# ## Finite fields

# In[42]:


p = next_prime(2^20)
R.<x> = GF(p)[]
R


# In[43]:


P = R.irreducible_element(20)
P


# In[44]:


K.<z> = GF(p^20, modulus=P)
K


# In[45]:


z^20


# ### If we don't care about the moduls

# In[46]:


L.<z> = GF(p^2)
L


# In[47]:


L.modulus()


# In[48]:


z.multiplicative_order()


# In[49]:


z^3


# In[50]:


e = L.primitive_element()
e.multiplicative_order()


# In[51]:


e


# In[52]:


e.minpoly()


# In[53]:


z.log(e)


# ## Elliptic curves

# In[54]:


E = EllipticCurve([1,2])
E


# In[55]:


E.j_invariant()


# In[56]:


E.torsion_order()


# In[57]:


E.torsion_points()


# In[58]:


G = E.torsion_subgroup()
G


# In[59]:


G.gens()


# ### Elliptic curves over finite fields

# In[60]:


E = EllipticCurve(GF(p), [0,1,0,2,3])
E


# In[61]:


E.cardinality().factor()


# In[62]:


P = E.random_point()
Q = E.lift_x(123)
P, Q


# In[63]:


P+Q


# In[64]:


Q.order().factor()


# In[65]:


R = 9*23*241*Q
R


# In[66]:


R.order()


# In[67]:


R.division_points(7)


# ### Cryptographic size
# 
# If you want to count the number of points of elliptic curves of cryptographic size, you need to install an optional package.
# 
# - Make sure that you have a stable connection to the internet,
# 
# - In a shell, type
# 
#   ~~~
#   sage -i database_pari
#   ~~~
# 
#   Alternatively, you can evaluate the cell below.
# 
# - Wait until installation is done, then restart SageMath.

# In[ ]:


get_ipython().system('sage -i database_pari')


# ## Isogenies

# In[68]:


phi = E.isogeny([R])
phi


# In[69]:


S = phi(P)
S


# In[70]:


S.parent()


# In[71]:


phi(R)


# In[72]:


phi.rational_maps()


# In[73]:


phi.kernel_polynomial()


# In[74]:


phi.kernel_polynomial()(R[0])


# ### Pairings

# In[75]:


L.<z> = GF(p^2)
EE = E.change_ring(L)
EE


# In[76]:


EE.cardinality().factor()


# In[77]:


T = EE.lift_x(912851*z + 87136)
T.order()


# In[78]:


w = T.weil_pairing(EE(R), 3)
w


# In[79]:


w.multiplicative_order()


# In[80]:


T.weil_pairing(2*T, 3)