Exponentiation Modulaire

L'exponentiation modulaire (aussi appelée powmod ou modpow en programmation) est le calcul d'une puissance entière suivi d'une réduction modulo un entier positif $ n $.

Mathématiquement, il s'agit de calculer $ a^b \mod n $ avec $ a $ la base, $ b $ l'exposant et $ n $ le modulo (entier strictement positif)

L'exponentiation modulaire est un outil fondamental en cryptographie moderne, notamment dans les systèmes à clé publique.

Le calcul revient à déterminer le reste de la division euclidienne de $ a^b $ par $ n $.

Une méthode directe consiste à calculer la puissance complète puis à en prendre le reste modulo $ n $.

Cependant, cette méthode devient rapidement impraticable car les valeurs de $ a^b $ croissent exponentiellement avec $ b $.

En pratique, il est préférable de réduire modulo $ n $ à chaque étape du calcul en utilisant la propriété $ x \equiv y \mod n $, alors $ x \cdot z \equiv y \cdot z \mod n $

Cette propriété permet d'effectuer des réductions intermédiaires et d'éviter la manipulation de nombres gigantesques.

Calculer les $ x $ derniers chiffres d'un nombre en écriture décimale revient à effectuer un calcul modulo $ 10^x $.

Cette propriété repose sur le fait que travailler modulo $ 10^x $ conserve exactement les $ x $ derniers chiffres en base 10.

L'algorithme le plus utilisé est l'exponentiation rapide modulaire, aussi appelée méthode square-and-multiply. Il repose sur l'écriture binaire de l'exposant $ e $.

En notant $ e=\sum_{i=0}^{m-1}a_{i}2^{i} $ sur $ m $ bits avec $ a_i $ les valeurs binaires (0 ou 1) dans l'écriture en base 2 de $ e $ (avec $ a_{m-1} = 1 $)

Alors $ b^e $ peut s'écrire $$ b^e = b^{\left( \sum_{i=0}^{n-1} a_i \cdot 2^i \right)} = \prod_{i=0}^{n-1} \left( b^{2^i} \right)^{a_i} $$

Et donc $$ b^e \mod n \equiv \prod_{i=0}^{n-1} \left( b^{2^i} \right)^{a_i} \mod n $$

Voici l'implémentation de l'exponentiation modulaire rapide en pseudocode :// pseudocode
function powmod(base b, exponent e, modulus m) {
r = 1
b = b % m
if (b == 0) return 0
while (e > 0) {
if (e % 2) r = (r * b) % m
e = e >> 1
b = (b ** 2) % m
}
return r
}

En théorie, l'algorithme d'exponentiation rapide est celui qui nécessite le moins d'étapes. Le nombre d'étapes dépend de la taille en bits de l'exposant $ b $.

Pour un calcul à la main, une méthode efficace consiste à :

— Décomposer l'exposant en puissances de 2

— Calculer successivement les carrés modulo $ n $

— Multiplier les puissances utiles (bits égaux à $ 1 $)

En pratique, pour les petites valeurs de $ a $, $ b $ et $ n $ calculer la puissance puis le modulo (avec une division euclidienne) est plus instinctif.

Ce calcul est connu sous le nom du problème du logarithme discret. Certaines solutions peuvent être trouvées par force brute mais il n'y a pas de solution générale triviale.

Les calculs utilisent des puissances et des modulos qui sont généralement définis sur l'ensemble des entiers naturels N.

Il est possible d'utiliser des nombres rationnels mais ce n'est pas géré ici.