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₀ := n
b₀ := b
t₀ := 0
t := 1
q := nombre entier immédiatement inférieur ou égal à n₀ / b₀
r := n₀ - q · b₀
Tant que r > 0 faire
   Début
      temp := t₀ - q · t
      Si temp >= 0 alors temp := temp mod n, sinon temp := n - ((-temp) mod n)
      t₀ := t
      t := temp
      n₀ := b₀
      b₀ := r
      q := nombre entier immédiatement inférieur ou égal à n₀ / b₀
      r := n₀ - q · b₀
   Fin
Si b₀ <> 1 alors b n'a pas d'inverse modulo n, sinon b^-1 mod n = t

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

Référence

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

Didier Müller, 29.10.01