Calculateur d'Exponentiation Modulaire

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

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 :

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

Comment utiliser le calculateur d'exponentiation modulaire

1. 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.
2. 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).
3. 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.
4. Cliquez sur Calculer : Le calculateur détermine a^b mod n via l'exponentiation binaire et affiche le résultat instantanément.
5. 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.
6. 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