Rechercher un outil
Exponentiation Modulaire

Outil de calcul de puissance modulaire. L'exponentiation modulaire (ou puissance modulo) est le résultat du calcul a^b modulo n. Elle est utilisée en informatique et en cryptographie.

Résultats

Exponentiation Modulaire -

Catégorie(s) : Arithmétique

Partager
Partager
dCode et plus

dCode est gratuit et ses outils sont une aide précieuse dans les jeux, les maths, les énigmes, les géocaches, et les problèmes à résoudre au quotidien !
Une suggestion ? un problème ? une idée ? Ecrire à dCode !


Rendez-vous sur notre communauté Discord dCode pour participer au forum d'entraide !
PS : Pour les messages codés, testez notre détecteur de chiffrement !


Grâce à vos remarques, réponses et commentaires pertinents, dCode peut développer le meilleur outil 'Exponentiation Modulaire', alors écrivez-nous c'est gratuit ! Merci !

Exponentiation Modulaire

Calcul de puissance a^b mod n




Solveur a^b mod n

Solveurs limités à des solutions entières < 10000

Trouver l'exposant b




Trouver la base a




Trouver le modulo n




Voir aussi : Solveur d'Equation

Réponses aux Questions (FAQ)

Qu'est-ce que l'exponentiation modulaire ? (Définition)

L'exponentiation modulaire (ou powmod, ou modpow) est un calcul sur des nombres entiers composé d'une puissance suivie d'un modulo. Ce type de calcul est très utilisé en cryptographie moderne.

Comment calculer une puissance d'un nombre modulo n ? (Principe de calcul)

Une méthode directe est de calculer la valeur de la puissance puis d'en extraire le modulo (le reste dans la division par n)

Exemple : Calculer $ 9^{10} \mod 11 $ c'est calculer $ 9^{10} = 3486784401 $ puis $ 3486784401 \mod 11 \equiv 1 $

En pratique, les nombres générés par les puissances sont gigantesques, et les mathématiciens et informaticiens utilisent des simplifications, notamment l'exponentiation rapide.

Le mot puissance indique le nom de l'opération, et le mot exposant indique l'opérande.

Comment calculer les derniers chiffres d'une puissance ?

Calculer les $ x $ derniers chiffres de $ a^b $ revient à calculer $ a^b \mod n $ avec $ n = 10^x $ (le nombre $ 1 $ suivi de $ x $ zéros)

Exemple : $ 3^9 = 19683 $ et $ 3^9 \mod 100 = 83 $ (les 2 derniers chiffres)

Quel est l'algorithme de powmod ?

Il existe plusieurs algorithmes, mais le plus efficace et appelé exponentiation rapide (modulaire), utilise une propriété sur l'écriture binaire de $ e $.

En notant $ e=\sum_{i=0}^{m-1}a_{i}2^{i} $ sur $ m $ bits avec $ a_i $ les valeurs binaires (0 ou 1) dans l'écriture en base 2 de $ e $ (avec $ a_{m-1} = 1 $)

Alors $ b^e $ peut s'écrire $$ b^e = b^{\left( \sum_{i=0}^{n-1} a_i \cdot 2^i \right)} = \prod_{i=0}^{n-1} \left( b^{2^i} \right)^{a_i} $$

Et donc $$ b^e \mod n \equiv \prod_{i=0}^{n-1} \left( b^{2^i} \right)^{a_i} \mod n $$

Voici l'implémentation de l'exponentiation modulaire rapide en pseudocode :// pseudocode
function powmod(base b, exponent e, modulus m) {
r = 1
b = b % m
if (b == 0) return 0
while (e > 0) {
if (e % 2) r = (r * b) % m
e = e >> 1
b = (b ** 2) % m
}
return r
}

Comment calculer a^b mod n à la main ?

En théorie, l'algorithme de powmod rapide (ci-dessus) est aussi celui qui a le moins d'étapes. Il a besoin de $ m $ étapes, avec $ m $ la taille en bits du nombre $ b $ en binaire.

En pratique, pour les petites valeurs de $ a $, $ b $ et $ n $ calculer la puissance puis le modulo (avec une division euclidienne) est plus instinctif.

Comment trouver l'exposant connaissant la base et le modulo ?

Ce calcul est connu sous le nom du problème du logarithme discret. Certaines solutions peuvent être trouvées par force brute mais il n'y a pas de solution générale triviale.

Pourquoi l'exponentiation modulaire est limitée aux entiers ?

Les calculs utilisent des puissances et des modulos qui sont généralement définis sur l'ensemble des entiers naturels N. Il est possible d'utiliser des nombres rationnels mais ce n'est pas géré ici.

Code source

dCode se réserve la propriété du code source pour "Exponentiation Modulaire". Sauf code licence open source explicite (indiqué Creative Commons / gratuit), l'algorithme pour "Exponentiation Modulaire", l'applet ou snippet (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou les fonctions liées à "Exponentiation Modulaire" (calculer, convertir, résoudre, décrypter / encrypter, déchiffrer / chiffrer, décoder / encoder, traduire) codés en langage informatique (Python, Java, C#, PHP, Javascript, Matlab, etc.) ou les données, en téléchargement, script, ou les accès API à "Exponentiation Modulaire" ne sont pas publics, idem pour un usage hors ligne, PC, mobile, tablette, appli iPhone ou Android !
Rappel : dCode est gratuit.

Citation

Le copier-coller de la page "Exponentiation Modulaire" ou de ses résultats est autorisée tant que vous citez dCode !
Citer comme source bibliographique :
Exponentiation Modulaire sur dCode.fr [site web en ligne], consulté le 05/10/2022, https://www.dcode.fr/exponentiation-modulaire

Besoin d'Aide ?

Rendez-vous sur notre communauté Discord dCode pour participer au forum d'entraide !
PS : Pour les messages codés, testez notre détecteur de chiffrement !

Questions / Commentaires

Grâce à vos remarques, réponses et commentaires pertinents, dCode peut développer le meilleur outil 'Exponentiation Modulaire', alors écrivez-nous c'est gratuit ! Merci !


https://www.dcode.fr/exponentiation-modulaire
© 2022 dCode — La 'boite à outils' indispensable qui sait résoudre tous les jeux / énigmes / géocaches / CTF.
 
Un problème ?