Calculateur d'Exponentiation Modulaire

Calculez efficacement l'exponentiation modulaire a^b mod n en utilisant l'algorithme d'exponentiation binaire (puissance rapide). Saisissez la base, l'exposant et le modulo pour obtenir des résultats instantanés avec une décomposition étape par étape de la méthode d'exponentiation par carré, une visualisation de la décomposition binaire et un contexte cryptographique.

Embed Calculateur d'Exponentiation Modulaire Widget

Calculateur d'Exponentiation Modulaire

Le calculateur d'exponentiation modulaire calcule \(a^b \bmod n\) — en élevant une base \(a\) à un exposant \(b\) et en prenant le reste de la division par le modulo \(n\). Il utilise l'algorithme d'exponentiation binaire (également appelé puissance rapide ou exponentiation par carrés), qui réduit l'opération de \(O(b)\) multiplications à seulement \(O(\log b)\). C'est le même algorithme utilisé dans les implémentations cryptographiques réelles comme RSA, Diffie-Hellman et ElGamal.

Applications de l'exponentiation modulaire

🔐

Chiffrement RSA

Chiffrer et déchiffrer des messages en utilisant l'exponentiation modulaire avec de grands produits de nombres premiers

🤝

Diffie-Hellman

Protocole d'échange de clés calculant g^a mod p pour des secrets partagés sécurisés

✍

Signatures numériques

DSA, ECDSA et EdDSA reposent tous sur l'exponentiation modulaire

🧪

Tests de primalité

Les tests de Fermat et Miller-Rabin utilisent a^(n-1) mod n pour vérifier la primalité

🏆

Programmation compétitive

L'arithmétique modulaire avec puissance rapide est essentielle pour les problèmes de concours

🔗

Blockchain

La preuve de travail et le hachage cryptographique reposent sur l'arithmétique modulaire

Comment fonctionne l'algorithme d'exponentiation binaire

L'idée clé est que nous pouvons décomposer n'importe quel exposant en une somme de puissances de 2 en utilisant sa représentation binaire. Par exemple, \(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\), donc \(a^{13} = a^{8} \times a^{4} \times a^{1}\).

L'algorithme traite les chiffres binaires de l'exposant de gauche à droite :

Étape 1 : Convertir l'exposant \(b\) en binaire.

Étape 2 : Initialiser le résultat = 1 (ou = base si le premier bit est 1).

Étape 3 : Pour chaque bit suivant : Élever le résultat au carré (mod n). Si le bit est 1, multiplier également par la base (mod n).

Étape 4 : Une fois tous les bits traités, le résultat est \(a^b \bmod n\).

Pseudocode

function modpow(base, exp, mod):
    result = 1
    base = base mod mod
    while exp > 0:
        if exp is odd:        // le bit est 1
            result = (result × base) mod mod
        exp = exp >> 1        // décalage à droite (diviser par 2)
        base = (base × base) mod mod
    return result

Formules clés

Propriété	Formule	Description
Exponentiation modulaire	\(a^b \bmod n\)	Reste de a^b divisé par n
Petit théorème de Fermat	\(a^{p-1} \equiv 1 \pmod{p}\)	Pour p premier et pgcd(a,p)=1
Théorème d'Euler	\(a^{\phi(n)} \equiv 1 \pmod{n}\)	Pour pgcd(a,n)=1, où φ est l'indicateur d'Euler
Complexité méthode binaire	\(O(\log b)\) multiplications	Au plus 2·log₂(b) multiplications modulaires
Chiffrement RSA	\(c = m^e \bmod n\)	Chiffrer le message m avec la clé publique (e, n)
Déchiffrement RSA	\(m = c^d \bmod n\)	Déchiffrer le cryptogramme c avec la clé privée d

Comment utiliser le calculateur d'exponentiation modulaire

Entrez la base (a) : C'est le nombre que vous souhaitez élever à une puissance. Il peut être positif ou négatif. Par exemple, entrez 7 pour calculer 7^256 mod 13.
Entrez l'exposant (b) : Doit être un entier non négatif. Il représente la puissance. Pour les applications cryptographiques, il peut être très grand (le calculateur supporte jusqu'à 10^18).
Entrez le modulo (n) : Doit être un entier positif. C'est le nombre par lequel vous divisez pour obtenir le reste. Dans RSA, c'est généralement le produit de deux grands nombres premiers.
Cliquez sur Calculer : Le calculateur détermine a^b mod n via l'exponentiation binaire et affiche le résultat instantanément.
Regardez l'animation : Appuyez sur Jouer pour voir l'algorithme d'exponentiation binaire s'exécuter étape par étape. Chaque bit de l'exposant est traité en séquence, montrant si l'algorithme élève au carré, ou élève au carré et multiplie.
Examinez la trace : Le tableau étape par étape montre chaque calcul intermédiaire, et la comparaison d'efficacité montre à quel point l'exponentiation binaire est plus rapide que la multiplication répétée naïve.

Pourquoi l'exponentiation binaire est rapide

Considérons le calcul de \(2^{1000} \bmod 13\). L'approche naïve nécessite 999 multiplications. L'exponentiation binaire convertit 1000 en binaire (1111101000), qui possède 10 bits. Elle nécessite au plus 9 élévations au carré plus quelques multiplications pour chaque bit '1' — environ 15 opérations au total. Cela représente environ 98,5 % d'opérations en moins. Pour des exposants à l'échelle cryptographique comportant des centaines de chiffres, la différence est astronomique : la méthode binaire prend des milliers d'opérations là où la méthode naïve nécessiterait plus d'opérations qu'il n'y a d'atomes dans l'univers.

FAQ

Qu'est-ce que l'exponentiation modulaire ?

L'exponentiation modulaire calcule (a^b) mod n — elle élève une base à un exposant, puis prend le reste de la division par un modulo. C'est l'opération centrale de la cryptographie à clé publique (RSA, Diffie-Hellman, ElGamal) et elle est largement utilisée en théorie des nombres, en programmation compétitive et en informatique. La méthode d'exponentiation binaire calcule cela efficacement en O(log b) multiplications.

Comment fonctionne l'exponentiation binaire (exponentiation par carrés) ?

L'exponentiation binaire convertit l'exposant en sa représentation binaire, puis traite chaque bit de gauche à droite (ou de droite à gauche). Pour chaque bit, elle élève le résultat actuel au carré modulo n. Si le bit est 1, elle multiplie en plus le résultat par la base modulo n. Cela réduit le nombre de multiplications de b−1 (méthode naïve) à au plus 2×log₂(b), ce qui rend le calcul possible avec des exposants énormes.

Pourquoi l'exponentiation modulaire est-elle importante en cryptographie ?

Le chiffrement RSA calcule c = m^e mod n pour le chiffrement et m = c^d mod n pour le déchiffrement, où n est un produit de deux grands nombres premiers et les exposants peuvent compter des centaines de chiffres. Sans une exponentiation modulaire rapide, ces opérations seraient informatiquement impossibles. La sécurité repose sur le fait que l'opération inverse (calculer le logarithme discret) est considérée comme informatiquement infaisable.

La base peut-elle être négative ?

Oui, les bases négatives sont entièrement prises en charge. Le calculateur réduit d'abord la base modulo n (en utilisant l'arithmétique modulaire de Python, qui renvoie toujours un résultat non négatif pour un n positif). Par exemple, (−3)^2 mod 7 = 9 mod 7 = 2. Les résultats négatifs ne se produisent jamais car la réduction modulaire produit toujours une valeur dans l'intervalle [0, n−1].

Que se passe-t-il lorsque le modulo est 1 ?

Tout entier modulo 1 est égal à 0. C'est parce que diviser n'importe quel entier par 1 donne l'entier lui-même avec un reste de 0. Ainsi, a^b mod 1 = 0 pour toutes les valeurs de a et b. Le calculateur traite cela comme un cas particulier.

Citez ce contenu, cette page ou cet outil comme suit :

"Calculateur d'Exponentiation Modulaire" sur https://MiniWebtool.com/fr/calculateur-exponentiation-modulaire/ de MiniWebtool, https://MiniWebtool.com/

par l'équipe miniwebtool. Mis à jour : 2026-04-16

Vous pouvez également essayer notre Résolveur Mathématique IA GPT pour résoudre vos problèmes mathématiques grâce à des questions-réponses en langage naturel.