Loading AI tools
De Wikipédia, l'encyclopédie libre
En mathématiques, plus précisément en arithmétique modulaire, l’exponentiation modulaire est un type d'élévation à la puissance (exponentiation) réalisée sur des entiers modulo un entier. Elle est particulièrement utilisée en informatique, spécialement dans le domaine de la cryptologie.
Etant donnés une base b, un exposant e et un entier non nul m, l'exponentiation modulaire consiste à calculer c tel que :
Par exemple, si b = 5, e = 3, et m = 13, le calcul de c donne 8.
Calculer l'exponentiation modulaire est considéré comme facile, même lorsque les nombres en jeu sont énormes. Au contraire, calculer le logarithme discret (trouver e à partir de b, c et m) est reconnu comme difficile. Ce comportement de fonction à sens unique fait de l'exponentiation modulaire une bonne candidate pour être utilisée dans les algorithmes de cryptologie.
Le calcul naïf de l'exponentielle modulaire est le suivant : on multiplie e fois le nombre b par lui-même, et une fois l'entier be obtenu, on calcule son reste modulo m via l'algorithme de division euclidienne. Cette méthode souffre de deux défauts :
La suite de l'article décrit ces différentes adaptations et discute leur efficacité en fonction notamment de la taille des données.
La méthode la plus directe pour calculer un exposant modulaire est de calculer be directement, puis de prendre ce nombre modulo m. Essayons de calculer c, avec b = 4, e = 13, et m = 497 :
Utilisons une calculatrice pour calculer 413, on obtient la valeur 67 108 864. Prenons celle-ci modulo 497, le résultat c obtenu est 445. Bien que b n'ait qu'un chiffre et e deux, la valeur be atteint une longueur de 8 chiffres.
En cryptologie forte, b a souvent au moins 256 chiffres binaires (77 chiffres décimaux). Prenons b = 5 × 1076 et e = 17, deux valeurs parfaitement raisonnables. Dans cet exemple, b a 77 chiffres décimaux et e deux, mais be a 1 304 chiffres. Ce genre de calculs est possible sur les ordinateurs modernes, mais l'énormité de ce genre de nombre ralentit considérablement la vitesse des calculs. A mesure que la taille de b et e augmente pour améliorer la sécurité du chiffrement, la valeur de be devient ingérable.
Le temps requis pour réaliser l'exponentiation dépend de l'environnement opératoire et du processeur. Le calcul de l'exponentiation par une série de multiplications requiert un temps O(e).
Une seconde méthode pour calculer l'exponentiation modulaire requiert plus d'opérations que la première méthode. En raison de l'exigence moindre de mémoire requise, les opérations prennent pourtant moins de temps que précédemment. Il en résulte que cet algorithme peut se montrer plus rapide :
Cet algorithme utilise le fait que, pour deux entiers donnés b et c, les premières relations impliquent la suivante :
L'algorithme suivant :
Notez qu'à chaque passage par l'étape 3, l'équation devient vraie. Lorsque l'étape 3 a été exécutée e fois, alors, c contient la réponse qui était cherchée.
Reprenons l'exemple b = 4, e = 13, et m = 497. L'algorithme passe par l'étape 3 treize fois :
La réponse finale pour c est par conséquent 445, comme dans la première méthode.
Comme la première méthode, ceci requiert un temps de calcul en O(e). Néanmoins, comme les nombres utilisés dans ces calculs sont plus petits que les nombres utilisés dans les calculs du premier algorithme, le facteur constant de cette méthode tend à être plus petit.
Une troisième méthode réduit drastiquement à la fois le nombre d'opérations et la place en mémoire nécessaires à l'exécution de l'exponentiation modulaire. C'est une combinaison de la méthode précédente et d'un principe plus général appelé exponentiation rapide (connue aussi sous le nom d'exponentiation par carré).
Tout d'abord il faut convertir l'exposant e en notation binaire, c'est-à-dire qu'on écrit :
Dans cette notation, la longueur de e est de n bits. ai peut prendre la valeur 0 ou 1 pour tout i tel que 0 ≤ i < n - 1. Par définition, an - 1 = 1.
La valeur be peut alors être écrite :
La solution c est, par conséquent :
Un tel algorithme peut être facilement implémenté dans un langage de programmation qui possède les surcharges d'opérateurs et les ramasse-miettes. L'exemple suivant est en C#. La classe Bignum représente un grand nombre positif arbitraire. Les variables d'entrée sont base pour la base (b), exp pour l'exposant (e), et m pour le module.
Bignum modpow(Bignum base, Bignum exp, Bignum m) { Bignum result = 1; while (exp > 0) { if ((exp & 1) > 0) result = (result * base) % m; exp >>= 1; base = (base * base) % m; } return result; }
Ce code, basé sur celui de la page 244 de Applied Cryptography de Bruce Schneier,2e éd. (ISBN 0471117099), utilise une boucle while pour exécuter tout le travail nécessaire au calcul de l'exponentiation modulaire.
Notez que lors de la première entrée dans la boucle, la variable base contient b. Ensuite, l'élévation au carré répétée à la troisième ligne de code assure qu'à la fin de chaque boucle, la variable base vaut , où i est le nombre d'itérations de la boucle. (Ce qui fait de i le prochain bit à traiter dans l'exposant binaire exp, dont le plus petit bit significatif est exp0).
La première ligne de code réalise simplement la multiplication dans . Si ai vaut zéro, le code n'est pas exécuté, ce qui équivaut à multiplier le total par un. Si par contre ai vaut un, le résultat est simplement multiplié par la variable base (contenant la valeur de la base originale).
Pour finir, testons avec l'exemple b = 4, e = 13, et m = 497. Notez que e est égal à 1101 en binaire. Comme e est d'une longueur de quatre chiffres binaires, la boucle ne s'exécutera que quatre fois :
La boucle termine alors, car exp est égal à zéro, et le résultat 445 est retourné. Ceci est en accord avec les deux algorithmes précédents.
Le temps d'exécution de cet algorithme est O(log e). Lorsqu'il travaille avec de grandes valeurs de e, il est bien plus rapide que les deux précédents algorithmes.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.