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

Autres outils connexes:

Opérations mathématiques avancées:

• Calculatrice d'Antilogarithme
• Calculatrice de la fonction bêta
• Calculateur de Coefficient Binomial
• Calculatrice de distribution binomiale
• Calculatrice de Bit
• Calculateur du Théorème Central Limite
• Calculatrice de Combinaison
• Calculatrice de Fonction d'Erreur Complémentaire
• Calculatrice de Nombres Complexes
• Calculatrice d'Entropie
• Calculatrice de fonction d'erreur
• Calculatrice de désintégration exponentielle
• Calculatrice de croissance exponentielle
• Calculatrice d'intégrale exponentielle
• calculatrice-des-exposants-haute-précision En vedette
• Calculatrice Factorielle
• Calculatrice de Fonction Gamma
• Calculateur de Nombre d'Or
• Calculatrice de demi-vie
• Calculatrice du Taux de Croissance en Pourcentage
• Calculatrice de permutation
• Calculatrice de Distribution de Poisson
• Calculatrice des racines de polynômes avec étapes détaillées
• Calculatrice de probabilité
• Calculatrice de Distribution de Probabilité
• Calculatrice de Proportion
• Calculatrice de Formule Quadratique En vedette
• Calculatrice Scientifique
• Calculatrice de notation scientifique
• Calculateur de Chiffres Significatifs Nouveau
• Calculatrice de Somme de Cubes
• Calculatrice de la somme des entiers positifs
• Calculatrice de la somme des carrés
• Générateur de table de vérité
• Calculateur de Théorie des Ensembles
• Générateur de Diagramme de Venn (3 Ensembles)
• Calculatrice du Théorème des Restes Chinois
• Calculatrice de la fonction indicatrice d'Euler
• Calculatrice de l'Algorithme Euclidien Étendu
• Calculatrice de l'Inverse Multiplicatif Modulaire
• Calculatrice de fractions continues
• Calculateur de plus court chemin de Dijkstra
• Calculateur d'arbre couvrant minimum
• Validateur de séquence de degrés de graphe
• Calculateur de Dérangement (Sous-factorielle)
• Calculateur de Nombres de Stirling
• Calculateur du principe des tiroirs
• Calculateur d'état stationnaire de chaîne de Markov
• Calculateur d'Arrondi Nouveau
• Calculateur de Distribution Binomiale Négative Nouveau
• Calculateur de Permutations avec Répétition Nouveau
• Calculateur d'Exponentiation Modulaire Nouveau
• Calculateur de Racine Primitive
• Simplificateur d'Algèbre de Boole Nouveau
• Solveur de Tableau de Karnaugh (K-Map) Nouveau
• Calculateur de Coloration de Graphes Nouveau
• Calculateur de Tri Topologique Nouveau
• Calculateur de Matrice d'Adjacence Nouveau
• Calculateur d'Inclusion-Exclusion Nouveau
• Solveur de Programmation Linéaire Nouveau
• Solveur du Voyageur de Commerce (TSP) Nouveau
• Vérificateur de Chemin Hamiltonien Nouveau
• Vérificateur de Graphe Planaire Nouveau
• Calculateur de Flot Maximal dans un Réseau Nouveau
• Solveur du Problème des Mariages Stables Nouveau
• Calculateur d'Ordre en Théorie des Groupes Nouveau
• Calculateur d’Anneaux et de Corps Nouveau