TP 2: Algorithme d'Euclide étendu

Environnement de travail

Ouvrir EduPython pour utiliser les modules numpy et numpy.linalg (pour linear algebra) de Python, pour utiliser Python comme assistant de calcul matriciel

Algorithme d'Euclide

Ecrire une fonction python euclide(a,b) qui retourne le pgcd de a et b

Exemples : $a = 70$ et $b = 42$ donc $d = 14$

Algorithme d'Euclide étendu

Comment trouver une combinaison linéaire de $a$ et $b$ donnant le pgcd de $a$ et $b$?

"A la main" on remonte dans la suite des divisions euclidiennes mais comment le faire faire par une machine ?

On écrit la suite des divisions euclidiennes jusqu'à obtenir le dernier reste nul

$r_{-1} = a = bq + r = r_0q+ r_1$

$r_0 = r_1q_2+ r_2$

..................

$ r_{n-2}= r_{n-1}q_{n} + r_{n}$

Nous avons ici une récurrence double, pour déterminer $r_n$ nous avons besoin des deux termes précédents et l'initialisation se fait avec les deux termes initiaux $r_{-1} = a$ et $r_{0 } = b $

Un tour de boucle fait passer de $(r_{n-1},r_n)$ à $(r_{n},r_{n+1})$

De plus l'invariant de boucle est que chaque reste $r_k$ soit une combinaison linéaire de $a$ et $b$

En partant de $r_{-1} = a = 1\times a + 0 \times b = u_{-1}a+v_{-1}b$ et $r_{0} = b = 0\times a + 1 \times b = u_0a+v_0b$, on veut construire par récurrence deux suites $(u_n)$ et $(v_n)$ telles que : $r_n = u_na+v_nb$ et $u_{-1} = 1$, $u_0 = 0$ et $v_{-1} = 0$, $v_0 = 1$, il nous reste à trouver une relation de récurrence reliant $w_n=(u_n,v_n)$ à $w_{n-1}=(u_{n-1},v_{n-1})$ et $w_{n-2}=(u_{n-2},v_{n-2})$

Vérifier que cette relation est $w_n = w_{n-2} - \lfloor\dfrac{r_{n-2}}{r_{n-1}}\rfloor w_{n-1}$

Ecrire l'algorithme d'Euclide étendu où un tour de boucle met à jour deux couples de variables $(r_{n-1},r_n) -> (r_{n},r_{n+1})$ et $(w_{n-1},w_n) -> (w_{n},w_{n+1})$

Le traduire en Python

Se familiariser avec numpy

Nous allons faire l'exercice suivant avec numpy : On cherche un polynôme qui annule la matrice $T$ définie par

La matrice $T = \begin{pmatrix} 1 & 1 &1\\ 0& 1 & 1\\ 0 & 0 &1 \end{pmatrix}$ est une liste de listes (ligne par ligne)

Recopier le code suivant et l'exécuter


import numpy as np

T = np.array([[1,1,1],[0,1,1],[0,0,1]])
#I est la matrice identité d'ordre 3
I = np.eye(3)
S = T - I
print(S)

Maintenant il s'agit de calculer $S^3$ et de vérifier que l'on obtient la matrice nulle. Une façon de faire est :

Recopier le code suivant et l'exécuter


import numpy as np

T = np.array([[1,1,1],[0,1,1],[0,0,1]])
#I est la matrice identité d'ordre 3
I = np.eye(3)
S = T - I
S2 = S.dot(S)
S3 = S2.dot(S)
#on peut faire aussi S3 = S.dot(S).dot(S)
print(S3)

Une autre façon est d'utiliser le module numpy.linalg


import numpy as np
import numpy.linalg as alg

T = np.array([[1,1,1],[0,1,1],[0,0,1]])
#I est la matrice identité d'ordre 3
I = np.eye(3)
S = T - I
S3 = alg.matrix_power(S,3)
print(S3)

Exercices

  1. Comme $S^3 = T^3 - 3T^2 +3T -I$ on a trouvé un polynôme qui annule $T$, ce qui nous permet ici de trouver l'inverse de $T$ le module numpy.linalg permet lorsqu'une matrice est inversible de calculer son inverse, en écrivant T ' = alg.inv(T)
  2. Vérifier que $T' = T^2 -3T +3I$

Algorithme d'Euclide étendu

On peut regarder l'algorithme d'Euclide étendu d'un point de vue matriciel où il s'agit de répéter le processus suivant : $ \begin{pmatrix} a\\ b \end{pmatrix} \to \begin{pmatrix} 0 & 1\\ 1& -(a//b) \end{pmatrix}\begin{pmatrix} a\\ b \end{pmatrix}$ où $a//b$ donne le quotient de la division euclidienne de $a$ par $b$

Exercices

  1. Ecrire une fonction euclide_etendu(a,b), sous forme vectorisée qui retourne sous forme de liste en premier le pgcd $d$ puis $u$ et $v$ tel que $au+bv = d$
  2. Test: a = 1292 et b = 798 on doit obtenir d = 38, u = -8 et v = 13