Qu'est-ce que le calculateur de puissance modulaire ?
Le calculateur de puissance modulaire calcule \((\text{base}^{\text{exposant}}) \bmod m\) — c'est-à-dire le reste obtenu après avoir élevé une base à une puissance puis divisé le résultat par un module. Cette opération unique, appelée exponentiation modulaire, est omniprésente en théorie des nombres et en cryptographie : elle est au cœur du chiffrement RSA, de l'échange de clés Diffie-Hellman, des tests de primalité et des fonctions de hachage. La calculer directement (en formant d'abord la puissance gigantesque, puis en prenant le reste) est impossible pour de grands exposants ; on emploie donc un algorithme rapide à la place.
Comment l'utiliser
Saisissez trois nombres entiers : la base, l'exposant (nul ou positif) et le module \(m\) (un entier positif strictement supérieur à 1). Cliquez sur calculer : l'outil renvoie un résultat compris entre 0 et \(m-1\). Les bases négatives sont automatiquement ramenées à leur résidu non négatif approprié.
La formule expliquée
La formule centrale est :
$$\text{result} = \text{Base}^{\text{Exponent}} \bmod \text{Modulus}$$Plutôt que de construire l'immense nombre \(\text{base}^{\text{exposant}}\), le calculateur utilise la méthode de l'élévation au carré et multiplication (aussi appelée exponentiation binaire). Il lit l'exposant en binaire. En partant d'un résultat égal à 1, il élève la base au carré modulo \(m\) de façon répétée ; chaque fois que le chiffre binaire courant de l'exposant vaut 1, il multiplie cette valeur élevée au carré dans le résultat en cours, en réduisant à nouveau modulo \(m\). Comme chaque nombre intermédiaire reste inférieur à \(m^2\), le calcul demeure rapide même pour des exposants comportant des centaines de chiffres.
Exemple concret
Calculons \(7^{256} \bmod 13\). L'ordre de 7 modulo 13 divise 12, et \(7^{12} \equiv 1\). Puisque \(256 = 12 \times 21 + 4\), on obtient $$7^{256} \equiv 7^4 = 2401 \equiv 9 \pmod{13}.$$ La réponse est donc 9 — trouvée instantanément ici, sans jamais former le nombre de 217 chiffres qu'est \(7^{256}\).
FAQ
Et si le module vaut 1 ? Tout entier est congru à 0 modulo 1, le résultat est donc 0.
L'exposant peut-il être 0 ? Oui. Toute base élevée à la puissance 0 vaut 1, donc le résultat est \(1 \bmod m\) (soit 1 lorsque \(m > 1\)).
Pourquoi ne pas calculer directement la puissance ? Pour de grands exposants, le nombre intermédiaire comporterait un nombre astronomique de chiffres et provoquerait un dépassement de capacité. La réduction modulo à chaque étape maintient les valeurs petites et rend la méthode efficace.
