Calculatrice d’exponentiation modulaire

📋

Étapes

Comment utiliser cette calculatrice

3 étapes

1

Saisissez la base, l’exposant et le modulo

Saisissez des nombres entiers pour la base (a), l’exposant (b) et le modulo (m). Les trois champs acceptent des entiers arbitrairement grands : la calculatrice utilise BigInt en interne, de sorte que les résultats restent exacts même au-delà de la limite normale des entiers sûrs de JavaScript, 2^53. La base peut être négative ; elle est automatiquement ramenée dans l’intervalle [0, m).

2

Lisez le résultat

L’onglet Résultat affiche a^b mod m dès que les trois champs sont renseignés. La ligne de détail reformule le calcul, par exemple : « 4^13 mod 497 = 445 ».

3

Examinez l’algorithme

Passez à l’onglet Étapes du carré et multiplication pour voir précisément comment l’algorithme d’exponentiation rapide aboutit à ce résultat, bit par bit. L’onglet Exposant binaire affiche le développement binaire de l’exposant qui détermine ces étapes, ainsi que le nombre de mises au carré et de multiplications effectuées.

⚡

Référence

Formule et méthodologie

1 formules

Carré et multiplication (exponentiation binaire)

result = a^b mod m, computed by scanning b's binary digits left to right

Initialisez le résultat à 1. Pour chaque bit de b, en commençant par le plus significatif, élevez le résultat au carré puis réduisez-le modulo m ; si le bit vaut 1, multipliez aussi le résultat par a et réduisez-le de nouveau modulo m. Après le dernier bit, le résultat est égal à a^b mod m. Comme b comporte environ log2(b) bits, il faut environ log2(b) mises au carré et au plus autant de multiplications — bien moins que les b−1 multiplications nécessaires à l’approche naïve qui consiste à multiplier a par lui-même b fois. Chaque valeur intermédiaire reste inférieure à m au lieu d’atteindre a^b avant la réduction.

📖

Glossaire

Termes clés expliqués

7 termes

Exponentiation modulaire Calcul de a^b mod m, c’est-à-dire du reste de la division de a élevé à la puissance b par m. C’est l’opération fondamentale du chiffrement RSA, de l’échange de clés Diffie-Hellman et de nombreux tests de primalité.

Carré et multiplication Algorithme d’exponentiation modulaire qui parcourt les bits de l’exposant et, pour chacun, élève au carré le résultat courant (puis le multiplie par la base lorsque le bit vaut 1), en réduisant modulo m après chaque opération. On l’appelle aussi exponentiation rapide ou binaire.

Exponentiation binaire Autre nom de la méthode du carré et multiplication, qui souligne que l’algorithme s’appuie sur la représentation en base 2 de l’exposant plutôt que de décrémenter b jusqu’à 0.

Modulo Diviseur m dans l’expression a mod m. Le résultat d’une exponentiation modulaire est toujours un entier de l’intervalle [0, m). Si le modulo vaut 1, tous les résultats valent 0, puisque tout entier est divisible par 1.

BigInt Type d’entier à précision arbitraire de JavaScript. Les nombres ordinaires de JavaScript perdent leur précision au-delà de 2^53 (environ 9 billiards) ; BigInt n’a pas cette limite, ce qui est essentiel pour les bases, exposants et modulos de taille cryptographique, qui peuvent compter des dizaines ou des centaines de chiffres.

Exponentiation rapide Synonyme de carré et multiplication ou d’exponentiation binaire, par opposition à l’approche naïve en O(b) par multiplications répétées. L’exponentiation rapide nécessite O(log b) multiplications.

RSA Cryptosystème à clé publique dont les opérations de chiffrement et de déchiffrement sont des exponentiations modulaires : texte chiffré = message^e mod n pour chiffrer, puis message = texte chiffré^d mod n pour déchiffrer. Les clés RSA réelles utilisent des modulos de plusieurs centaines de chiffres ; d’où l’importance de l’exponentiation modulaire rapide, compatible avec BigInt.

👥

Situations types

Exemples concrets

3 exemples

🧮

Exemple vérifiable à la main

4^13 mod 497

Base (a) 4 Exposant (b) 13 Modulo (m) 497

13 s’écrit 1101 en binaire : l’exposant comporte quatre bits, donc l’algorithme effectue quatre mises au carré et trois multiplications (une pour chaque bit égal à 1). Le résultat courant passe par 1 → 4 → 16 → 65 (après multiplication) → 79 → 445 (après la dernière multiplication), et aboutit à 445. Vérification directe : 4^13 = 67,108,864, et la division de 67,108,864 par 497 laisse un reste de 445.

🔐

Chiffrement RSA de démonstration

65^17 mod 3233

Base (a) 65 Exposant (b) 17 Modulo (m) 3233

Il s’agit de l’exemple classique donné dans la description originale de RSA : n = 3233 est le produit de deux petits nombres premiers (61 et 53), l’exposant public vaut 17 et le chiffrement du message 65 produit le texte chiffré 2790. Les clés RSA réelles utilisent un modulo de plusieurs centaines de chiffres plutôt que cet exemple miniature à 4 chiffres, mais l’opération — l’exponentiation modulaire — est identique. C’est pourquoi la calculatrice utilise BigInt partout et non des nombres ordinaires.

⚠️

Cas limite

Toute base et tout exposant, module = 1

Base (a) 123456789 Exposant (b) 999999 Modulo (m) 1

Tout entier est congru à 0 modulo 1 ; a^b mod 1 vaut donc toujours 0, quelles que soient les valeurs de a et de b. Dans ce cas, l’onglet Étapes du carré et multiplication n’affiche aucune étape puisqu’il n’y a rien à calculer : le résultat est déterminé d’avance.

🔗

Référence

Citer cette calculatrice

APA et MLA

Utilisez un de ces formats pour citer cette calculatrice dans un devoir ou un rapport.

APA

MLA

📄

Analyse approfondie

Comprendre l’exponentiation modulaire

3 chapitres · 4 min de lecture

L’exponentiation modulaire — le calcul de a^b mod m — ressemble à un simple exercice d’arithmétique, mais son efficacité rend possible la cryptographie moderne à clé publique. Cette calculatrice évalue a^b mod m à l’aide de l’algorithme du carré et multiplication et en présente le fonctionnement, bit par bit.

Pourquoi ne pas calculer simplement a^b puis prendre le reste ?

Pour de petits nombres, calculer directement a^b puis réduire modulo m fonctionne bien. Mais les opérations cryptographiques utilisent des exposants et des modulos de plusieurs centaines de chiffres : a^b aurait lui-même bien plus de chiffres qu’il n’y a d’atomes dans l’univers observable, avant même d’arriver à l’étape « mod m ». La méthode du carré et multiplication évite ce problème en réduisant modulo m après chaque mise au carré et chaque multiplication ; aucune valeur intermédiaire ne dépasse donc m. Comme elle nécessite aussi environ log2(b) multiplications au lieu de b − 1, des opérations telles que le chiffrement RSA avec un exposant de 2048 bits peuvent s’effectuer en quelques millisecondes plutôt que d’être pratiquement impossibles à calculer.

Lire les onglets Étapes et Exposant binaire

L’algorithme parcourt les bits de l’exposant du plus significatif au moins significatif. À chaque bit, il élève au carré le résultat courant et le réduit modulo m ; si le bit vaut 1, il multiplie aussi par la base, puis réduit de nouveau. L’onglet Exposant binaire indique quels bits valent 1 et lesquels valent 0 : chaque bit 1 entraîne une multiplication supplémentaire, en plus de la mise au carré effectuée pour chaque bit. Même si sa valeur décimale est très grande, un exposant de 20 bits ne demande que 20 mises au carré et au plus 20 multiplications.

Limites et cas particuliers

Cette calculatrice n’accepte que des exposants non négatifs. Un exposant négatif, par exemple a^(-1) mod m, nécessite de calculer l’inverse modulaire de a. Cet inverse n’existe que si a et m sont premiers entre eux et se calcule au moyen d’un autre algorithme, celui d’Euclide étendu ; cette opération n’est pas prise en charge ici. Un modulo égal à 1 donne toujours 0, puisque tout entier est divisible par 1. Enfin, même si la base saisie est négative, elle est ramenée dans l’intervalle [0, m) avant le calcul, conformément à la convention mathématique selon laquelle a mod m est toujours non négatif.

❓

Questions

Questions fréquentes

6 questions

Quelle formule utilise la calculatrice d’exponentiation modulaire ?+

Elle calcule a^b mod m avec la méthode du carré et multiplication. En partant d’un résultat égal à 1, elle parcourt les bits de l’exposant b du plus significatif au moins significatif, élève le résultat courant au carré à chaque bit et le réduit modulo m ; lorsque le bit vaut 1, elle le multiplie aussi par la base, puis le réduit de nouveau modulo m.

Pourquoi le carré et multiplication est-il plus rapide que la méthode évidente ?+

Multiplier a par lui-même b − 1 fois demande O(b) multiplications ; pour un exposant de 100 chiffres, cela représenterait un nombre astronomique d’étapes. La méthode du carré et multiplication n’effectue qu’environ log2(b) mises au carré et au plus autant de multiplications. Un exposant de 100 chiffres ne demande ainsi que quelques centaines d’opérations : quelques millisecondes au lieu d’un calcul qui ne finirait jamais.

Pourquoi cette calculatrice a-t-elle besoin de BigInt plutôt que des nombres ordinaires ?+

Les nombres ordinaires de JavaScript perdent leur précision au-delà de 2^53 (environ 9 billiards). Les bases, exposants et modulos utilisés en cryptographie comptent souvent des dizaines ou des centaines de chiffres, bien au-delà de cette limite. BigInt n’a pas de limite de précision supérieure ; les champs, les valeurs intermédiaires et le résultat restent donc exacts, quelle que soit la taille des entrées.

Où utilise-t-on concrètement l’exponentiation modulaire ?+

C’est une opération fondamentale du chiffrement et du déchiffrement RSA (texte chiffré = message^e mod n), de l’échange de clés Diffie-Hellman, des signatures numériques et de plusieurs tests de primalité, comme ceux de Fermat et de Miller-Rabin. Chaque utilisation de HTTPS s’appuie en coulisses sur une exponentiation modulaire rapide.

Puis-je saisir un exposant négatif ?+

Non. Un exposant négatif nécessiterait de calculer d’abord l’inverse modulaire de la base, qui n’existe que si la base et le modulo sont premiers entre eux ; cette opération fait appel à un algorithme entièrement différent. La calculatrice signale les exposants négatifs au lieu d’afficher silencieusement un résultat incorrect ou trompeur.

Que se passe-t-il si je règle le modulo sur 1 ?+

Le résultat vaut toujours 0, quelle que soit la base ou l’exposant : par définition, tout entier est congru à 0 modulo 1. La calculatrice renvoie directement ce résultat sans exécuter l’algorithme.

Téléchargez instantanément un PDF d’une page contenant vos résultats. Indiquez votre adresse e-mail pour recevoir également, de temps à autre, des conseils sur nos calculatrices — sans spam et avec désinscription possible à tout moment. Confidentialité.

Inputs

Result

How square-and-multiply works

Exponent in binary

Comment utiliser cette calculatrice

Saisissez la base, l’exposant et le modulo

Lisez le résultat

Examinez l’algorithme

Formule et méthodologie

Termes clés expliqués

Exemples concrets

Exemple vérifiable à la main

Chiffrement RSA de démonstration

Cas limite

Citer cette calculatrice

Comprendre l’exponentiation modulaire

Pourquoi ne pas calculer simplement a^b puis prendre le reste ?

Lire les onglets Étapes et Exposant binaire

Limites et cas particuliers

Questions fréquentes

Obtenez un PDF personnalisé de vos résultats

Calculatrice d’exponentiation modulaire

Inputs

Result

How square-and-multiply works

Exponent in binary

Comment utiliser cette calculatrice

Saisissez la base, l’exposant et le modulo

Lisez le résultat

Examinez l’algorithme

Formule et méthodologie

Termes clés expliqués

Exemples concrets

Citer cette calculatrice

Comprendre l’exponentiation modulaire

Pourquoi ne pas calculer simplement a^b puis prendre le reste ?

Lire les onglets Étapes et Exposant binaire

Limites et cas particuliers

Questions fréquentes

Obtenez un PDF personnalisé de vos résultats

Explorer davantage

Calculateurs associés

Guides et articles