Le calcul $a^b \pmod{n}$ est la clé de voûte de la sécurité informatique mondiale (Cryptographie RSA, échanges de clés Diffie-Hellman). Quand $b$ est gigantesque, il est impossible de calculer d'abord la puissance classique pour en prendre le reste. On utilise un algorithme d'exponentiation modulaire rapide.
Trouvez le reste de la division de $Base^{Exposant}$ par le $Modulo$.
Si vous voulez calculer $5^{117} \pmod{19}$, une calculatrice classique plantera car $5^{117}$ est un nombre tellement géant qu'il ne rentre pas en mémoire. La ruse consiste à calculer les puissances de 2 successives (en décomposant l'exposant en binaire) et de prendre le modulo à chaque étape intermédiaire pour que les nombres ne grossissent jamais.
Théorèmes très utiles :
Le système RSA chiffre vos messages avec un calcul modulaire. Il est facile de chiffrer en faisant une puissance modulaire géante. Mais il est mathématiquement infernal de faire l'inverse (trouver le message d'origine) si l'on ne connait pas les facteurs premiers du modulo (qui est un produit de deux nombres premiers titanesques).