Calculateur d'exponentiation modulaire

Q: Comment calculer une puissance modulo m à la main ?

Utilisez la méthode « élever au carré et multiplier ». Réduisez d'abord la base : remplacez b par b bmod m. Écrivez ensuite l'exposant en binaire et élevez la base au carré de façon répétée, en réduisant modulo m à chaque étape : b^2, b^4, b^8, b^16, ldots. Multipliez enfin uniquement les valeurs obtenues qui correspondent aux bits 1 de l'exposant, en réduisant modulo m à chaque fois. Chaque nombre intermédiaire reste ainsi inférieur à m^2.

Q: Pourquoi le résultat de b^e mod m est-il toujours compris entre 0 et m-1 ?

Parce que l'arithmétique modulaire travaille avec les résidus non négatifs minimaux. L'expression b^e bmod m désigne par définition le reste de la division de b^e par m, et les restes d'une division vérifient toujours 0 ≤ c ≤ m-1. Même si la base est négative, elle est d'abord convertie en son résidu positif équivalent : la réponse n'est donc jamais négative.

Q: Quel est le dernier chiffre d'une grande puissance (par exemple 7^100) ?

Il s'agit d'une exponentiation modulaire déguisée : le dernier chiffre d'un nombre est ce nombre modulo 10. Calculez donc 7^100 bmod 10 ici. De même, les deux derniers chiffres correspondent à la valeur modulo 100, et les trois derniers à la valeur modulo 1000. C'est un raccourci classique pour les exercices d'olympiades et les devoirs portant sur les chiffres finaux.

Q: Que se passe-t-il si l'exposant vaut 0 ou si le module vaut 1 ?

Avec e = 0, le résultat est 1 bmod m, qui vaut 1 pour tout module sauf m = 1, où il vaut 0 — puisque tout entier est congru à 0 modulo 1. Ces cas limites sont traités correctement, et m = 1 renvoie toujours 0, quels que soient la base et l'exposant : c'est mathématiquement exact, et non une erreur.

Q: Peut-on utiliser une base ou un exposant négatif ?

Les bases négatives ne posent aucun problème : le calculateur les réduit d'abord à un résidu positif équivalent, de sorte que -12 se comporte comme m - 12. Les exposants négatifs ne sont pas pris en charge, car ils exigeraient l'inverse modulaire de la base, qui n'existe que si gcd(b, m) = 1. Pour contourner cela, déterminez d'abord b^-1 bmod m, puis élevez ce résultat à la puissance |e|.

Q: Comment l'exponentiation modulaire est-elle utilisée dans RSA et en cryptographie ?

Le chiffrement et le déchiffrement RSA se réduisent chacun à une seule exponentiation modulaire c = m^e bmod n avec un module de 2048 bits ou plus — exactement ce que la méthode « élever au carré et multiplier » calcule efficacement. L'échange de clés Diffie–Hellman et ElGamal fonctionnent de la même façon. La rapidité en O(log e) de la méthode rend les exposants gigantesques envisageables, tandis que la difficulté d'inverser l'opération sans la clé secrète garantit la sécurité de ces schémas.

Q: Quelle est l'erreur courante lorsqu'on calcule b^e mod m ?

L'erreur la plus fréquente consiste à calculer b^e d'abord et à prendre le reste ensuite — la puissance devient très vite astronomique et dépasse les capacités d'une calculatrice, voire devient impossible à écrire. Réduisez toujours modulo m après chaque élévation au carré et chaque multiplication. Autre oubli classique : b^0 bmod 1 = 0, et non 1, car tout entier est congru à 0 modulo 1.

Mis à jour : 15.10.2026

Calcule b^e mod m instantanément, même lorsque l'exposant compte des centaines de chiffres, grâce à l'exponentiation rapide par élévations au carré successives. Saisissez une base, un exposant non négatif et un module positif, et visualisez, si vous le souhaitez, chaque étape d'élévation au carré.

Calculer une puissance modulo m

Formule de l'exponentiation modulaire

Formule

\[ c \;=\; b^e \bmod m \] \[ e = \sum_{k=0}^{n} e_k\,2^k \;\;\Longrightarrow\;\; b^e \;\equiv\; \prod_{k:\; e_k = 1} \bigl(b^{2^k} \bmod m\bigr) \pmod{m}, \qquad b^{2^k} \equiv \bigl(b^{2^{k-1}}\bigr)^2 \pmod{m} \]

Où :

\(b\) — la base (un entier quelconque) ;
\(e\) — l'exposant (un entier non négatif) ;
\(m\) — le module (un entier strictement positif) ;
\(e_k\) — les bits de \(e\) dans son écriture binaire ;
\(c\) — le résultat : le reste de la division de \(b^e\) par \(m\).

La première ligne définit l'exponentiation modulaire. La deuxième est l'identité d'exponentiation binaire (« élever au carré et multiplier ») qu'utilise le calculateur : l'exposant est décomposé en puissances de deux, les puissances \(b^{2^k}\) sont obtenues par élévations au carré successives, et seules celles correspondant aux bits égaux à 1 sont multipliées entre elles — le tout modulo \(m\), si bien que les nombres intermédiaires ne deviennent jamais démesurés.

Exponentiation modulaire — Exemple de calcul

Exemple : calculons \(3^{644} \bmod 645\), les valeurs préremplies du calculateur. L'entier \(3^{644}\) compte 308 chiffres : calculer d'abord la puissance puis la réduire est voué à l'échec.

Étape 1 — réduire la base : \(3 \bmod 645 = 3\).

Étape 2 — écrire l'exposant en binaire :

\[ 644 = 512 + 128 + 4 = 1010000100_2 \]

Les élévations au carré successives modulo 645 donnent \(3^4 \equiv 81\), \(3^{128} \equiv 396\) et \(3^{512} \equiv 111 \pmod{645}\) pour les bits égaux à 1.

Étape 3 — multiplier ces valeurs en réduisant modulo 645 à chaque fois :

\[ 3^{644} \equiv 81 \times 396 \times 111 \equiv 471 \times 111 \equiv 52281 \equiv 36 \pmod{645} \]

Résultat : \(3^{644} \bmod 645 = 36\). L'algorithme n'a nécessité que 9 élévations au carré et 3 multiplications — soit 12 opérations modulaires au lieu des 643 qu'exigerait une méthode naïve.

Comment utiliser le calculateur

Saisissez la Base (b) — un entier quelconque, positif ou négatif.
Saisissez l'Exposant (e) — un entier non négatif. Il peut être tellement grand que \(b^e\) soit impossible à calculer directement ; c'est précisément pour cela que cet outil existe.
Saisissez le Module (m) — un entier strictement positif.
Laissez cochée l'option Afficher les étapes d'élévation au carré si vous souhaitez obtenir l'écriture binaire de l'exposant et un tableau de chaque élévation au carré ; décochez-la pour n'obtenir que le résultat.
Consultez le Résultat (bᵉ mod m), la Base réduite (b mod m) et le déroulé détaillé étape par étape.

Qu'est-ce que l'exponentiation modulaire ?

L'exponentiation modulaire répond à la question : quel est le reste de la division de \(b^e\) par \(m\) ? Le résultat est toujours compris entre \(0\) et \(m-1\). Autrement dit, c'est l'entier \(c\) vérifiant \(0 \le c < m\) et \(b^e \equiv c \pmod{m}\). Par exemple, \(3^{644} \bmod 645 = 36\) signifie que la division de \(3^{644}\) par 645 laisse un reste de 36.

La méthode naïve — calculer \(b^e\) puis prendre le reste — échoue très vite. \(3^{644}\) compte déjà 308 chiffres, et la cryptographie utilise couramment des exposants de plusieurs centaines de chiffres, pour lesquels \(b^e\) compterait plus de chiffres qu'il n'y a d'atomes dans l'univers. La solution est la méthode « élever au carré et multiplier » : écrire l'exposant en binaire, obtenir \(b^{2^k} \bmod m\) en élevant au carré et en réduisant à chaque étape, puis multiplier entre elles uniquement les valeurs correspondant aux bits égaux à 1. Il ne faut alors que \(O(\log e)\) multiplications modulaires au lieu de \(e-1\), et comme chaque résultat intermédiaire est réduit modulo \(m\), aucun nombre ne dépasse jamais environ \(m^2\).

L'exponentiation modulaire est le cheval de bataille de la cryptographie à clé publique. Le chiffrement et le déchiffrement RSA se ramènent chacun à une seule exponentiation modulaire avec un module gigantesque ; l'échange de clés Diffie–Hellman et le schéma ElGamal en dépendent aussi. Elle est également au cœur des tests de primalité comme ceux de Fermat et de Miller–Rabin, qui vérifient si \(a^{n-1} \equiv 1 \pmod n\) — vous pouvez explorer la théorie des nombres sous-jacente avec nos calculateurs Petit théorème de Fermat et Théorème d'Euler.

L'affichage des étapes rend l'algorithme transparent : le tableau présente chaque position de bit \(k\) de l'exposant face à \(b^{2^k} \bmod m\), les lignes en gras sont celles effectivement utilisées, et leur produit (réduit modulo \(m\)) est la réponse. C'est exactement ce que font en interne les systèmes de calcul formel, et le voir à l'œuvre une fois est la meilleure façon de comprendre pourquoi les exposants gigantesques ne coûtent presque rien.

Hypothèses, limites et conseils

L'exposant doit être non négatif. Un exposant négatif exigerait l'inverse modulaire de \(b\), qui n'existe que si \(\gcd(b, m) = 1\). Pour traiter ce cas, déterminez d'abord l'inverse avec notre calculateur d'Inverse modulaire, puis utilisez son résultat comme base avec un exposant positif.
Le module doit être positif. Si \(m = 1\), tout entier est congru à 0, donc le résultat est 0 — c'est mathématiquement correct, et non une erreur.
Les bases négatives ne posent aucun problème. La base est d'abord réduite à son résidu non négatif \(b \bmod m\) : \(-12\) et \(m - 12\) donnent donc la même réponse.
Un exposant nul donne \(1 \bmod m\) (qui vaut 0 uniquement si \(m = 1\)), en cohérence avec \(b^0 = 1\).
Limites de taille : la base et le module peuvent compter jusqu'à 1000 chiffres chacun, et l'exposant peut atteindre \(10^{18}\). L'algorithme étant logarithmique en l'exposant, même cette valeur est traitée instantanément.
Vérifiez vos résultats par un autre chemin : pour un module composé, vous pouvez découper le calcul en puissances de nombres premiers puis recombiner les résultats — essayez notre calculateur du Théorème des restes chinois pour vérifier vos résultats indépendamment.

Questions fréquentes

Comment calculer une puissance modulo m à la main ?

Utilisez la méthode « élever au carré et multiplier ». Réduisez d'abord la base : remplacez b par \(b \bmod m\). Écrivez ensuite l'exposant en binaire et élevez la base au carré de façon répétée, en réduisant modulo m à chaque étape : \(b^2, b^4, b^8, b^{16}, \ldots\). Multipliez enfin uniquement les valeurs obtenues qui correspondent aux bits 1 de l'exposant, en réduisant modulo m à chaque fois. Chaque nombre intermédiaire reste ainsi inférieur à \(m^2\).

Pourquoi le résultat de b^e mod m est-il toujours compris entre 0 et m-1 ?

Parce que l'arithmétique modulaire travaille avec les résidus non négatifs minimaux. L'expression \(b^e \bmod m\) désigne par définition le reste de la division de \(b^e\) par \(m\), et les restes d'une division vérifient toujours \(0 \le c \le m-1\). Même si la base est négative, elle est d'abord convertie en son résidu positif équivalent : la réponse n'est donc jamais négative.

Quel est le dernier chiffre d'une grande puissance (par exemple 7^100) ?

Il s'agit d'une exponentiation modulaire déguisée : le dernier chiffre d'un nombre est ce nombre modulo 10. Calculez donc \(7^{100} \bmod 10\) ici. De même, les deux derniers chiffres correspondent à la valeur modulo 100, et les trois derniers à la valeur modulo 1000. C'est un raccourci classique pour les exercices d'olympiades et les devoirs portant sur les chiffres finaux.

Que se passe-t-il si l'exposant vaut 0 ou si le module vaut 1 ?

Avec \(e = 0\), le résultat est \(1 \bmod m\), qui vaut 1 pour tout module sauf \(m = 1\), où il vaut 0 — puisque tout entier est congru à 0 modulo 1. Ces cas limites sont traités correctement, et \(m = 1\) renvoie toujours 0, quels que soient la base et l'exposant : c'est mathématiquement exact, et non une erreur.

Peut-on utiliser une base ou un exposant négatif ?

Les bases négatives ne posent aucun problème : le calculateur les réduit d'abord à un résidu positif équivalent, de sorte que \(-12\) se comporte comme \(m - 12\). Les exposants négatifs ne sont pas pris en charge, car ils exigeraient l'inverse modulaire de la base, qui n'existe que si \(\gcd(b, m) = 1\). Pour contourner cela, déterminez d'abord \(b^{-1} \bmod m\), puis élevez ce résultat à la puissance \(|e|\).

Comment l'exponentiation modulaire est-elle utilisée dans RSA et en cryptographie ?

Le chiffrement et le déchiffrement RSA se réduisent chacun à une seule exponentiation modulaire \(c = m^e \bmod n\) avec un module de 2048 bits ou plus — exactement ce que la méthode « élever au carré et multiplier » calcule efficacement. L'échange de clés Diffie–Hellman et ElGamal fonctionnent de la même façon. La rapidité en \(O(\log e)\) de la méthode rend les exposants gigantesques envisageables, tandis que la difficulté d'inverser l'opération sans la clé secrète garantit la sécurité de ces schémas.

Quelle est l'erreur courante lorsqu'on calcule b^e mod m ?

L'erreur la plus fréquente consiste à calculer \(b^e\) d'abord et à prendre le reste ensuite — la puissance devient très vite astronomique et dépasse les capacités d'une calculatrice, voire devient impossible à écrire. Réduisez toujours modulo m après chaque élévation au carré et chaque multiplication. Autre oubli classique : \(b^0 \bmod 1 = 0\), et non 1, car tout entier est congru à 0 modulo 1.