Qu'est-ce que l'exponentiation modulaire ?
L'exponentiation modulaire calcule \(a^b \bmod m\) — le reste obtenu lorsque la puissance \(a^b\) est divisée par le module \(m\). C'est l'une des opérations les plus essentielles de la théorie des nombres et de la cryptographie : elle est au cœur d'algorithmes comme RSA, l'échange de clés Diffie–Hellman et les signatures numériques. Même lorsque \(a^b\) atteint des proportions astronomiques, le résultat modulo \(m\) reste petit et facile à calculer.
Comment utiliser ce calculateur
Saisissez trois nombres entiers : la base \(a\), l'exposant \(b\) (positif ou nul) et le module \(m\) (un entier strictement positif). Cliquez sur calculer pour obtenir l'unique reste compris entre 0 et \(m-1\). La base peut être négative : elle est d'abord ramenée dans l'intervalle de résidus valide avant l'exponentiation.
La formule expliquée
$$\text{result} = \text{Base } a^{\text{Exponent } b} \bmod \text{Modulus } m$$
Calculer \(a^b\) directement est impossible pour de grandes valeurs de \(b\). Cet outil emploie donc la méthode du carré et multiplication (aussi appelée exponentiation rapide ou binaire). L'exposant est lu en binaire. En partant d'un résultat \(r = 1\) et de la base réduite \(\bmod m\), on élève la base au carré \((\bmod m)\) pour chaque bit de l'exposant ; dès qu'un bit vaut 1, on multiplie le résultat par la base \((\bmod m)\). Cela ne demande qu'environ \(\log_2(b)\) multiplications au lieu de \(b\).
Exemple détaillé
Calculons \(4^{13} \bmod 497\). L'exposant 13 s'écrit 1101 en binaire. Déroulons la méthode du carré et multiplication : $$4^1 = 4,\quad 4^2 = 16,\quad 4^4 = 256,\quad 4^8 = 256^2 = 65536 \equiv 30 \pmod{497}.$$ Comme \(13 = 8 + 4 + 1\), on multiplie les puissances correspondantes : $$30 \times 256 \times 4 = 30720 \equiv 445 \pmod{497}.$$ Ainsi \(4^{13} \bmod 497 = \) 445.
FAQ
Et si l'exposant vaut 0 ? Tout nombre élevé à la puissance 0 vaut 1, donc le résultat est \(1 \bmod m\) (soit 0 lorsque \(m = 1\)).
La base peut-elle être négative ? Oui. Une base négative est d'abord convertie en son résidu positif équivalent \(\bmod m\), si bien que la réponse est toujours comprise entre 0 et \(m-1\).
Pourquoi ne pas simplement calculer \(a^b\) puis prendre le modulo ? Pour des tailles cryptographiques, \(a^b\) compterait des millions de chiffres. Réduire \(\bmod m\) à chaque étape maintient les nombres petits et le calcul rapide.
