Méthode pour calculer efficacement a^e modulo m pour des entiers a, exponent e (non négatif ou représenté en binaire) et un module m, en combinant l'élévation au carré répétée et la réduction modulaire pour limiter la taille des intermédiaires.

Principe

Utiliser la décomposition binaire (ou fenêtre glissante) de l'exposant pour effectuer des carrés successifs et des multiplications conditionnelles, en appliquant la réduction modulo après chaque opération afin d'éviter une croissance exponentielle des valeurs intermédiaires.

Démonstration

Calculer 2^20 mod 17. On a 2^4 = 16 ≡ −1 (mod 17), donc 2^20 = (2^4)^5 ≡ (−1)^5 = −1 ≡ 16 (mod 17). L'élévation par carrés successifs calcule 2, 4, 16, 1, ... avec réduction à chaque étape.

Mauvaise application

Effectuer l'exponentiation en précision entière avant la réduction (risque de débordement) ou utiliser une multiplication répétée naïve pour des exposants très grands sans décomposition, rendant le calcul impraticable.

Conséquence

Bien utilisée, elle permet de calculer rapidement de grandes puissances modulaires avec une complexité en temps logarithmique en e, supportant chiffrement, vérification de signatures et tests de primalité.

Inversion

La réversion conceptuelle consiste à tenter de retrouver l'exposant ou la base à partir de la puissance modulaire (logarithme discret), un problème inverse souvent difficile ; l'exponentiation modulaire est facile, son inverse est dur.

Limite

S'applique à l'exponentiation dans Z/mZ et plus généralement dans des groupes finis ; les exposants négatifs exigent des inverses modulaires (existence liée à la primo‑mutualité). Ne résout pas les logarithmes discrets ni l'exponentiation non modulaire.

Tension sémantique

Se distingue de l'exponentiation simple suivie d'une réduction (conceptuellement équivalente mais impraticable) et de l'exponentiation en arithmétique réelle où la réduction n'a pas de sens ; souvent confondue avec des protocoles de puissance sûrs.

Synthèse

L'exponentiation modulaire est la séquence contrôlée de mises au carré et multiplications avec réduction immédiate, guidée par la représentation binaire de l'exposant, pour calculer efficacement a^e mod m.