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

# <div class="alert alert-block alert-info">
# <center><font size=5><b>TP n°8 : Arithmétique - éléments de correction</b></font></center></div>

# $\require{color}$
# $\require{xcolor}$
# $\require{cancel}$
# $\newcommand{\myfbox}[1]{\fcolorbox{red}{white}{$\textrm{#1}$}}$
# $\require{stmaryrd}$
# $\newcommand{\ient}{[\![}$
# $\newcommand{\rrbracket}{]\!]}$
# $\newcommand{\llbracket}{[\![}$
# $\newcommand{\fient}{]\!]}$
# $\newcommand{\R}{\mathbb R}$
# $\newcommand{\K}{\mathbb K}$
# $\newcommand{\N}{\mathbb N}$
# $\newcommand{\C}{\mathbb C}$
# $\newcommand{\P}{\mathbb P}$
# $\newcommand{\E}{\mathbb E}$
# $\newcommand{\V}{\mathbb V}$
# $\newcommand{\Z}{\mathbb Z}$
# $\newcommand{\dt}{\mathrm d}$
# $\newcommand{\sh}{\operatorname{sh}}$
# $\newcommand{\ch}{\operatorname{ch}}$
# $\newcommand{\th}{\operatorname{th}}$
# $\newcommand{\e}{\operatorname{e}}$
# $\newcommand{\id}{\operatorname{Id}}$
# $\newcommand{\mat}{\operatorname{mat}}$
# $\newcommand{\sp}{\operatorname{Sp}}$
# $\newcommand{\In}{\operatorname{I}}$
# $\newcommand{\vect}{\operatorname{Vect}\ }$
# $\newcommand{\rg}{\operatorname{rg}}$
# $\newcommand{\tr}{\operatorname{Tr}}$
# $\newcommand{\dis}{\displaystyle}$
# $\renewcommand{\Im}{\operatorname{Im}}$
# $\newcommand{\im}{\operatorname{Im}}$
# $\newcommand{\bordermatrix}[3]{ \begin{matrix} \begin{matrix}#1\end{matrix} & \\  #3  & \hspace{-1em} \begin{matrix}#2\end{matrix} \end{matrix}}$
# $\newcommand{\fonction}[5]{#1\ \colon \left\{\begin{array}{ccl}#2 & \longrightarrow & #3\\#4 & \longmapsto & #5\end{array}\right.}$
# $\newcommand{\fonctionsansnom}[4]{\left\{\begin{array}{ccl}#1 & \longrightarrow & #2\\#3 & \longmapsto & #4\end{array}\right.}$
# $\newcommand{\revdots}{\mathinner{\mkern1mu\raise1pt{\kern7pt\hbox{.}}\mkern2mu\raise4pt\hbox{.}\mkern2mu\raise7pt\hbox{.}\mkern1mu}}$
# $\newcommand{\tendvers}[2]{\xrightarrow[#1\to#2]{}}$
# $\newcommand{\q}[1]{\mathbf{Q#1}\  \triangleright}$
# $\newcommand{\nicefrac}[2]{^{#1}/_{#2}}$

# In[1]:


import matplotlib.pyplot as plt
plt.rcParams['figure.figsize'] = [15, 8] # pour des plots plus grands
import numpy as np
import sympy as sp


# # <u>1 - Nombres premiers</u>

# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 1 : Test naïf de primalité</b></font>
# </div>

# In[2]:


def est_premier(n: int) -> bool:
    """
    Teste si n est premier (algorithme naif)
    """
    if n <= 1:
        return False
    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False
    return True


# In[3]:


est_premier(12)


# In[4]:


est_premier(19)


# In[5]:


[i for i in range(21) if est_premier(i)]


# > Pour compter (naïvement) le nombre de nombres premiers inférieurs (ou égaux) à 1000, on peut procéder de la manière suivante :

# In[6]:


cpt = 0
for i in range(2, 1001):
    if est_premier(i):
        cpt += 1
print(cpt)


# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 2 : Crible d'Ératosthène</b></font>
# </div>

# In[7]:


def crible(N: int) -> [bool]:
    """
    Implémente le crible D'Eratosthène
    """
    # Initialisation
    C = [False] * 2 + (N - 1) * [True]
    
    # Parcours du crible
    for n in range(2, int(N**0.5) + 1):
        if C[n]:
            for k in range(2 * n, N + 1, n):
                C[k] = False
    return C


# In[8]:


crible(10)


# > On peut obtenir la liste des premiers nombres premiers de la manière suivante :

# In[9]:


N = 21
C = crible(N)
print([i for i in range(N) if C[i]])


# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:47%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 3 : Théorème des nombres premiers</b></font>
# </div>

# In[10]:


X, Y = [], []
p = 0
N = 100

# tracé de la courbe représentative de pi
for n in range(N):
    if est_premier(n):
        p += 1
    X.append(n)
    Y.append(p)

plt.plot(X, Y, "b.", label=r"$x\mapsto \pi(x)$")

# tracé de la courbe représentative de x->x/ln(x)

X = np.linspace(2, N)
Y2 = X / np.log(X)
plt.plot(X, Y2, label=r"$x\mapsto \dfrac{x}{\ln(x)}$")

# tracé de la courbe représentative de x->int_{2}^{x} 1/ln(t)dt

t = sp.Symbol('t')
Li = lambda x: sp.integrate(1 / sp.log(t), (t, 2, x))
Y3 = [Li(x) for x in X]
plt.plot(X, Y3, label=r"$x\mapsto \int_{2}^{x}\dfrac{1}{\ln(t)}\mathrm{d}t$")

# option de tracé
plt.legend()
plt.grid()
plt.axis("equal")
plt.show()


# Il semble donc que l'on ait l'encadrement suivant :
# $$
# \fbox{$\forall x\geqslant 12,\ \frac{x}{\ln(x)} \leqslant \pi(x) \leqslant \int_{2}^{x}\dfrac{1}{\ln(t)}\mathrm{d}t$}
# $$

# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 4 : Spirale d'Ulam</b></font>
# </div>

# In[11]:


n = 100
N = n**2

X = []
Y = []
abscisse = 0
ordonnee = 0

nb = 1
cpt = 1
signex = 1
signey = 1

while nb < N:
    for i in range(cpt):
        abscisse = abscisse + signex
        nb += 1
        if est_premier(nb):
            X.append(abscisse)
            Y.append(ordonnee)
    signex *= -1
    for i in range(cpt):
        ordonnee = ordonnee + signey
        nb += 1
        if est_premier(nb):
            X.append(abscisse)
            Y.append(ordonnee)
    signey *= -1
    cpt+=1

plt.scatter(X,Y,s=10)
#plt.axis("off")
plt.axis("equal")
plt.show()


# In[12]:


def nb_diviseurs(n: int) -> int:
    """
    Renvoie le nombre de diviseurs de l'entier n
    """
    d = 2
    for k in range(2, n):
        if n % k == 0:
            d += 1
    return d


# In[13]:


n = 100
N = n**2

X = []
Y = []
S = []
abscisse = 0
ordonnee = 0

nb = 1
cpt = 1
signex = 1
signey = 1

while nb < N:
    for i in range(cpt):
        abscisse = abscisse + signex
        nb += 1
        X.append(abscisse)
        Y.append(ordonnee)
        S.append(nb_diviseurs(nb) / 10)
    signex *= -1
    for i in range(cpt):
        ordonnee = ordonnee + signey
        nb += 1
        X.append(abscisse)
        Y.append(ordonnee)
        S.append(nb_diviseurs(nb) / 10)
    signey *= -1
    cpt += 1

plt.scatter(X, Y, S)
plt.axis("off")
plt.axis("equal")
plt.show()


# # <u>2 - Algorithmes d'Euclide</u>

# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 5 : Algorithme d'Euclide étendu</b></font>
# </div>

# > On code d'abord l'algorithme d'Euclide classique :

# In[14]:


def euclide(a: int, b: int) -> int:
    """
    Entrée : deux entiers naturels a et b tels que a >= b
    Sortie : pgcd(a,b)
    """
    assert(a >= b)
    while b != 0:
        a, b = b, a%b
    return a


# In[15]:


euclide(35, 25)


# In[16]:


euclide(42, 13)


# In[17]:


euclide(48, 0)


# > On adapte la fonction précédente pour implémenter l'algorithme d'Euclide étendu ; il faut rajouter la gestion des suites $(u_n)$ et $(v_n)$, qui sont des suites récurrentes doubles, et donc nécessitent d'utiliser 2 variables chacune pour stocker leurs termes consécutifs :

# In[18]:


def euclidex(a: int, b: int) -> (int):
    """
    Entrée : deux entiers naturels a et b tels que a >= b
    Sortie : pgcd(a,b) et coefficients de Bezout associes
    """
    assert (a >= b)
    u, uu, v, vv = 1, 0, 0, 1
    while b != 0:
        q = a // b # on le stocke pour ne pas le calculer 2 fois
        u, uu, v, vv = uu, u - q * uu, vv, v - q * vv
        a, b = b, a % b
    return a, u, v


# In[19]:


euclidex(35, 25)


# In[20]:


a, b = 42, 13
pgcd, u, v = euclidex(a, b)
print(a * u + b * v == pgcd)


# # <u>3 - Chiffrement RSA</u>

# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 6 : RSA</b></font>
# </div>

# À vous de voir si vous êtes motivés... ou pas !