===== Inverse modulaire =====

Les techniques de chiffrement font usage des calculs avec modulo. Connaissant les nombres entiers $a > 1$ et $p > a$ premier, on a parfois besoin de trouver $u$ vérifiant $a \times u \mod p = 1$.

{{page>nsi:terminales:chiffrement_modulo#Rappel de ce qu'est modulo}}

===== Algorithme d'Euclide étendu =====

On exploite des propriétés arithmétiques importantes. L'une d'elle est le **théorème de Bézout** qui nous dit :

<WRAP tip>
Soient $a, b \in \mathbb{N}$, on peut trouver $u, v \in \mathbb{Z}$ tels que $a\cdot u + b\cdot v = PGCD(a,b)$.
</WRAP>

[[https://fr.wikipedia.org/wiki/Algorithme_d%27Euclide_%C3%A9tendu|Wikipedia]] nous donne l'algorithme d'Euclide étendu que je reproduis ici (presque) à l'identique :

<code lang-none>
ENTRÉES : a, b entiers (naturels)
SORTIES : r entier (naturel) et  u, v entiers relatifs tels que r = pgcd(a, b) et r = a*u+b*v

r, u, v, r', u', v' = a, 1, 0, b, 0, 1

TANT QUE r' ≠ 0 FAIRE
    q = r÷r' 
    r, u, v, r', u', v' = r', u', v', r - q *r', u - q*u', v - q*v'
FIN TANT QUE
RENVOYER r, u, v
</code>

<WRAP important>Le symbole ''÷'' représente une division entière, c'est à dire ''%%//%%'' en Python.</WRAP> 

<WRAP tip>
L'algorithme d'Euclide normal est celui qui permet de calculer le PGCD. Cet algorithme est un peu plus complet puisqu'il donne en plus les valeurs de ''u'' et ''v''.

Il y a une infinité de paires ''u,v''. Cet algorithme nous renvoie donc **une de ces paires**. C'est justement celle dont nous avons besoin.
</WRAP>

===== Application à notre cas =====

Nous voulons trouver $u$ entier tel que $a\cdot u \mod p = 1$, avec $0 \leqslant u < p$.

$p$ est premier, donc $PGCD(a,p) = 1$ donc nous cherchons $u$ tel que $a\cdot u \mod p = PGCD(a,p)$, ce qui revient à dire $a\cdot u + p\cdot v = PGCD(a,p)$ pour un certain entier $v$.

Cela correspond au théorème de Bézout et à l'algorithme d'Euclide étendu. La valeur de ''u'' renvoyée est justement celle que nous voulons.

===== À faire =====

Vous devez écrire en Python une fonction ''%%inverse_modulaire(a, p)%%'' qui reprend l'algorithme d'Euclide étendu en tenant compte des adaptations :

  * Au lieu de ''b'', nous voulons ''p'',
  * Au lieu de renvoyer ''%%(r, u, v)%%'', nous ne voulons que ''u''

Pour vérifier :

<code python>
# 6 * 9 = 54 donc 6 * 9 % 53 = 1
assert inverse_modulaire(6,53) == 9
# dans le même genre...
assert inverse_modulaire(18,53) == 3
assert inverse_modulaire(51,53) == 26
assert inverse_modulaire(52,53) == 52
assert inverse_modulaire(1,53) == 1
</code>