L'algorithme d'Euclide étendu

L'algorithme d'Euclide étendu permet de calculer l'inverse de b modulo n s'il existe.
Rappelons que l'inverse modulo n de b est le nombre entier b^-1 tel que b·b^-1 (mod n) = 1. Par exemple 7 est l'inverse modulo 9 de 4, car 4·7 (mod 9) = 28 (mod 9) = 1.

n_o := n
b_o := b
t_o := 0
t := 1
q := nombre entier immédiatement inférieur ou égal à n_o / b_o
r := n_o - q · b_o
Tant que r > 0 faire
   Début
      temp := t_o - q · t
      Si temp

0 alors temp := temp mod n, sinon temp := n - ((-temp) mod n)
      t_o := t
      t := temp
      n_o := b_o
      b_o := r
      q := nombre entier immédiatement inférieur ou égal à n_o / b_o
      r := n_o - q · b_o
   Fin
Si b_o

1 alors b n'a pas d'inverse modulo n, sinon b^-1 mod n = t

Exemple

Calculons 5^-1 mod 77. Pour faciliter les calculs, faisons un tableau que nous remplirons ligne par ligne.

n₀	b₀	r	q	t₀	t	temp = (t₀ - q·t) mod 77
77	5	2	15	0	1	62 = -15 + 77
5	2	1	2	1	62	31 = -123 + 77 + 77
2	1	0	2	62	31

STOP, car r = 0. Comme b₀ = 1, 5 a un inverse modulo 77, qui vaut 31.

Le programme ci-dessous utilise l'algorithme d'Euclide étendu:

Exercices

Appliquez à la main l'algorithme d'Euclide étendu pour faire les calculs suivants:

13^-1 mod 27
12^-1 mod 27
8^-1 mod 27

Vous vérifierez vos résultats avec le programme ci-dessus.

Programmation

Ecrivez un programme Python qui applique l'algorithme d'Euclide étendu, en écrivant toutes les étapes du tableau. Solution.

Référence

Stinson Douglas, Cryptographie - Théorie et pratique, Vuibert Informatique, Paris, 2001, p. 105

Didier Müller, 28.1.21