TP n°8 : Arithmétique - éléments de correction

$\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

1 - Nombres premiers¶

Exercice 1 : Test naïf de primalité

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)

Out[3]:

False

In [4]:

est_premier(19)

Out[4]:

True

In [5]:

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

Out[5]:

[2, 3, 5, 7, 11, 13, 17, 19]

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)

Exercice 2 : Crible d'Ératosthène

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)

Out[8]:

[False, False, True, True, False, True, False, True, False, False, False]

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]])

[2, 3, 5, 7, 11, 13, 17, 19]

Exercice 3 : Théorème des nombres premiers

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$} $$

Exercice 4 : Spirale d'Ulam

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()

2 - Algorithmes d'Euclide¶

Exercice 5 : Algorithme d'Euclide étendu

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)

Out[15]:

In [16]:

euclide(42, 13)

Out[16]:

In [17]:

euclide(48, 0)

Out[17]:

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)

Out[19]:

(5, -2, 3)

In [20]:

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

True

3 - Chiffrement RSA¶

Exercice 6 : RSA

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