Exponentiation Modulaire

L'exponentiation modulaire (ou powmod, ou modpow) est un calcul sur des nombres entiers composé d'une puissance suivie d'un modulo. Ce type de calcul est très utilisé en cryptographie moderne.

Une méthode directe est de calculer la valeur de la puissance puis d'en extraire le modulo (le reste dans la division par n)

En pratique, les nombres générés par les puissances sont gigantesques, et les mathématiciens et informaticiens utilisent des simplifications, notamment l'exponentiation rapide.

Calculer les $ x $ derniers chiffres de $ a^b $ revient à calculer $ a^b \mod n $ avec $ n = 10^x $ (le nombre $ 1 $ suivi de $ x $ zéros)

Il existe plusieurs algorithmes, mais le plus efficace et appelé exponentiation rapide (modulaire), utilise une propriété sur l'écriture binaire de $ 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 de powmod rapide (ci-dessus) est aussi celui qui a le moins d'étapes. Il a besoin de $ m $ étapes, avec $ m $ la taille en bits du nombre $ b $ en binaire.

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.