Exponentiation Modulaire

Exponentiation modulaire

En mathématiques, plus précisément en arithmétique modulaire, l'exponentiation modulaire est un type d'élévation à la puissance (exponentiation) exécutée modulo un entier. Elle est particulièrement utilisée en informatique, spécialement dans le domaine de la cryptologie.

Généralement, les problèmes d'exponentiation modulaire prennent forme avec une base donnée b, un exposant e, un entier m. On souhaite calculer c comme ceci :

$c \equiv b^e \pmod{m}$

Si b, e, et m sont positifs et b < m, alors l'unique solution c existe et possède la propriété $0\leq c\leq m$ . Par exemple, on donne b = 5, e = 3, et m = 13, la solution c qui marche est 8.

Les problèmes d'exponentiation modulaires similaires à l'exemple précédent sont considérés comme faciles à résoudre, même si les nombres en jeu sont énormes. Au contraire, calculer le logarithme discret (trouver b à partir de c, e 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.

Présentation générale

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 b^e obtenu, on calcule son reste modulo m via l'algorithme de division euclidienne. Cette méthode souffre de deux défauts :

d'une part, le nombre de multiplications peut facilement être réduit, par la méthode générale d'exponentiation rapide : il n'y aura plus que log(e) multiplications à effectuer.
d'autre part, on ne profite pas de la structure d'anneau du domaine dans lequel on travaille : les entiers modulo m. Or, cette structure autorise que les calculs soient faits directement dans cet anneau, sans passage au préalable par les entiers. Pour mettre en œuvre cette idée, il faut en pratique, à chaque nouvelle multiplication effectuée, calculer un nouveau reste modulo m. On rajoute ainsi de nouvelles opérations (pour chaque multiplication, une division euclidienne), mais on gagne par ailleurs du fait que la taille des données à manipuler est limitée par celle de m.

Une description de ces différentes adaptations, et une discussion de leur efficacité en fonction notamment de la taille des données, fait l'objet de la suite de l'article.

Méthode directe

La méthode la plus directe pour calculer un exposant modulaire est de calculer b^e directement, puis de prendre ce nombre modulo m. Essayons de calculer c, avec b = 4, e = 13, et m = 497:

$c \equiv 4^{13} \ \pmod{497}$

On peut utiliser une calculatrice pour calculer 4¹³; ceci a pour valeur 67 108 864. Prenons celle-ci modulo 497, la réponse c est déterminée et est égale à 445.

Notez que b a seulement une longueur de un chiffre et que e a seulement une longueur de deux chiffres, mais la valeur b^e a une longueur de 10 chiffres.

En cryptologie forte, b a souvent au moins 256 chiffres binaires (77 chiffres décimaux). Prenons b = 5 × 10⁷⁶ et e = 17, les deux ont des valeurs parfaitement raisonnables. Dans cet exemple, b a une longueur de 77 chiffres et e a une longueur de 2 chiffres, mais la valeur de b^e a une longueur de 1 304 chiffres décimaux. Ce genre de calculs sont possibles sur les ordinateurs modernes, mais l'absolue énormité de ce genre de nombre ralentit considérablement la vitesse des calculs. Comme b et e augmentent même de plus en plus pour donner une meilleure sécurité, la valeur b^e devient impraticable.

Le temps requis pour exécuter l'exponentiation dépend de l'environnement opératoire et du processeur. Si l'exponentiation est exécutée comme une série de multiplications, alors ceci requiert O(e) de temps pour être achevée.

Méthode utilisant moins de mémoire

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 :

soit par de moindres échanges entre cache (antémémoire) et mémoire
soit par une moindre utilisation du swapping dans le cas de mémoire virtuelle

Cet algorithme utilise le fait que, pour deux entiers donnés b et c, les premières relations impliquent la suivante :

$b^{\prime} \equiv b \ \pmod{m} \ {\rm et} \ c^{\prime}\equiv c\ \pmod{m}$

$b^{\prime} c^{\prime} \equiv bc \ \pmod{m}$

L'algorithme suivant :

Fixer c = 1, e' = 0.
Augmenter e' par 1.
Fixer $c \equiv (b \cdot c) \ \pmod{m}$ .
Si e' < e, aller à l'étape 2. Sinon, c contient la solution correcte de $c \equiv b^e \pmod{m}$ .

Notez qu'à chaque passage de l'étape 3, l'équation $c \equiv b^{e'} \ \pmod{m}$ 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 :

e' = 1. c = (1 × 4) (497) = 4 (497) = 4.
e' = 2. c = (4 × 4) (497) = 16 (497) = 16.
e' = 3. c = (16 × 4) (497) = 64 (497) = 64.
e' = 4. c = (64 × 4) (497) = 256 (497) = 256.
e' = 5. c = (256 × 4) (497) = 1024 (497) = 30.
e' = 6. c = (30 × 4) (497) = 120 (497) = 120.
e' = 7. c = (120 × 4) (497) = 480 (497) = 480.
e' = 8. c = (480 × 4) (497) = 1920 (497) = 429.
e' = 9. c = (429 × 4) (497) = 1716 (497) = 225.
e' = 10. c = (225 × 4) (497) = 900 (497) = 403.
e' = 11. c = (403 × 4) (497) = 1612 (497) = 121.
e' = 12. c = (121 × 4) (497) = 484 (497) = 484.
e' = 13. c = (484 × 4) (497) = 1936 (497) = 445.

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 O(e) de temps pour être achevé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 dans cette méthode tend à être plus petit.

La méthode la plus efficace

Une troisième méthode qui réduit drastiquement et le nombre d'opérations et la place en mémoire requiert d'améliorer l'exponentiation modulaire. Elle est une combinaison de la méthode précédente et d'un principe plus général appelé exponentiation binaire (connue aussi comme exponentiation par carré).

Premièrement, il est requis que l'exposant e soit converti en notation binaire. Ceci étant, e peut être écrit :

$e = \sum_{i=0}^{n-1} a_i 2^i$

Dans cette notation, la longueur de e est de n bits. a_i peut prendre la valeur 0 ou 1 pour n'importe quel i comme ceci 0 ≤ i < n - 1. Par définition, a_{n - 1} = 1.

La valeur b^e peut alors être écrite :

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

La solution c est, par conséquent :

$c \equiv \prod_{i=0}^{n-1} \left( b^{2^i} \right) ^ {a_i} \ \pmod{m}$

Comme un algorithme peut être facilement implémenté dans un langage de programmation qui inclut les priorités d'opérateurs et la mise en réserve(?). L'exemple suivant est en C#. La classe Bignum représente un grand nombre positif arbitraire. Les données base est la base (b), exp est l'exposant (e), et m est 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 ceci à la page 244 de Applied Cryptography de Bruce Schneier, 2e, ISBN 0471117099, utilise une simple boucle while pour exécuter tout le travail nécessaire pour calculer l'exponentiation modulaire.

Notez qu'une fois la boucle entrée pour la première fois, le code variable base est équivalent à b. Néanmoins, l'élévation au carré répétée à la troisième ligne de code assure ceci à la fin de chaque boucle, la variable base est équivalente à $b^{2^i}\ \pmod{m}$ , où i est le nombre d'itérations de la boucle. (Ceci donne pour i le prochain bit à travailler de l'exposant binaire exp, où le plus petit bit significatif est exp₀).

La première ligne de code transporte simplement la multiplication dans $\prod_{i=0}^{n-1} \left( b^{2^i} \right) ^ {a_i}\ \pmod{m}$ . Si a_i est zéro, aucun code n'exécute ceci effectivement, multipliant le total par un. Si a_i est, par exemple, un, la variable base (contenant la valeur $b^{2^i}\ \pmod{m}$ de la base originale) est simplement multipliée dedans.

Finalement, l'exemple b = 4, e = 13, et m = 497 sera essayé dans ce test. Notez que e est égal à 1101 en base deux. Parce que e est d'une longueur de quatre chiffres, la boucle s'exécutera seulement quatre fois :

Une fois être entré dans la boucle pour la première fois, les valeurs des variables sont les suivantes : base = 4, exp = 1101 (binaire), et result = 1. Comme le bit le plus à droite de exp est 1, result est changé en (1 × 4) % 497, c'est-à-dire 4. exp est ensuite tronqué à droite pour devenir 110 (binaire), et base élevée au carré pour être (4 × 4) % 497, c'est-à-dire 16.
Lors de la deuxième exécution de la boucle, le bit le plus à droite de exp est 0, result n'est donc pas modifié. exp est ensuite tronqué à droite pour devenir 11 (binaire), et base est élevé au carré pour être (16 × 16) % 497, c'est-à-dire 256.
Lors de la troisième exécution de la boucle, le bit le plus à droite de exp est 1. result est changé en (4 × 256) % 497, c'est-à-dire 30. exp est ensuite tronqué à droite pour devenir 1, et base est élevée au carré pour être (256 × 256) % 497, c'est-à-dire 429.
Lors de la quatrième exécution de la boucle, le bit le plus à droite de exp est 1. result est changé en (30 × 429) % 497, c'est-à-dire 445. exp est ensuite tronqué à droite pour devenir 0, et base est élevée au carré pour être (429 × 429) % 497, c'est-à-dire 151.

La boucle termine alors, comme 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.

Portail de la cryptologie

Ce document provient de « Exponentiation modulaire ».

Catégories : Cryptologie | Théorie algorithmique des nombres

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Exponentiation Modulaire de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

Exponentiation modulaire — En mathématiques, plus précisément en arithmétique modulaire, l exponentiation modulaire est un type d élévation à la puissance (exponentiation) exécutée modulo un entier. Elle est particulièrement utilisée en informatique, spécialement dans le… … Wikipédia en Français
Exponentiation Rapide — L exponentiation rapide est un algorithme utilisé pour calculer rapidement, de grandes puissances entières. En anglais, cette méthode est aussi appelée square and multiply (« mettre au carré et multiplier »). Sommaire 1 Écriture… … Wikipédia en Français
Exponentiation rapide — L exponentiation rapide est un algorithme utilisé pour calculer rapidement, de grandes puissances entières. En anglais, cette méthode est aussi appelée square and multiply (« mettre au carré et multiplier »). Sommaire 1 Écriture… … Wikipédia en Français
Arithmetique modulaire — Arithmétique modulaire Couverture de l’édition originale des Recherches arithmétiques de Gauss, livre fondateur de l’arithmétique modulaire. En mathématiques et plus précisément en théorie algébrique des nombres, l’arithmétique modulaire est un… … Wikipédia en Français
Arithmétique Modulaire — Couverture de l’édition originale des Recherches arithmétiques de Gauss, livre fondateur de l’arithmétique modulaire. En mathématiques et plus précisément en théorie algébrique des nombres, l’arithmétique modulaire est un ensemble de méthodes… … Wikipédia en Français
Arithmétique modulaire (synthèse) — Arithmétique modulaire Couverture de l’édition originale des Recherches arithmétiques de Gauss, livre fondateur de l’arithmétique modulaire. En mathématiques et plus précisément en théorie algébrique des nombres, l’arithmétique modulaire est un… … Wikipédia en Français
Arithmétique modulaire — Couverture de l’édition originale des Recherches arithmétiques de Gauss, livre fondateur de l’arithmétique modulaire. En mathématiques et plus précisément en théorie algébrique des nombres, l’arithmétique modulaire est un ensemble de méthodes… … Wikipédia en Français
Arithmétique modulo — Arithmétique modulaire Couverture de l’édition originale des Recherches arithmétiques de Gauss, livre fondateur de l’arithmétique modulaire. En mathématiques et plus précisément en théorie algébrique des nombres, l’arithmétique modulaire est un… … Wikipédia en Français
Sécurité matérielle des cartes à puce — La sécurité matérielle des cartes à puce et des autres microcontrôleurs est l un des éléments clefs de la sécurité des informations sensibles qu ils manipulent. La littérature scientifique a produit un grand nombre de publications visant à… … Wikipédia en Français
Rivest Shamir Adleman — Adi Shamir, un des auteurs de RSA. Rivest Shamir Adleman (presque toujours abrégé en RSA) est un algorithme de cryptographie asymétrique, très utilisé dans le commerce électronique, et plus généralement pour échanger des données confidentielles… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Exponentiation Modulaire