Exponentiation modulaire

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 :

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

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

L'algorithme suivant :

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

À chaque passage par l'étape 3, l'équation ${\displaystyle 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 = (4 x 1) (mod 497) = 4 (mod 497) = 4.
• e' = 2. c = (4 x 4) (mod 497) = 16 (mod 497) = 16.
• e' = 3. c = (4 x 16) (mod 497) = 64 (mod 497) = 64.
• e' = 4. c = (4 x 64) (mod 497) = 256 (mod 497) = 256.
• e' = 5. c = (4 x 256) (mod 497) = 1024 (mod 497) = 30.
• e' = 6. c = (4 x 30) (mod 497) = 120 (mod 497) = 120.
• e' = 7. c = (4 x 120) (mod 497) = 480 (mod 497) = 480.
• e' = 8. c = (4 x 480) (mod 497) = 1920 (mod 497) = 429.
• e' = 9. c = (4 x 429) (mod 497) = 1716 (mod 497) = 225.
• e' = 10. c = (4 x 225) (mod 497) = 900 (mod 497) = 403.
• e' = 11. c = (4 x 403) (mod 497) = 1612 (mod 497) = 121.
• e' = 12. c = (4 x 121) (mod 497) = 484 (mod 497) = 484.
• e' = 13. c = (4 x 484) (mod 497) = 1936 (mod 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 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 :

${\displaystyle 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 tout i tel que 0 ≤ i < n - 1. Par définition, a_{n - 1} = 1.

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

${\displaystyle 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 :

${\displaystyle c\equiv \prod _{i=0}^{n-1}\left(b^{2^{i}}\right)^{a_{i}}\ {\pmod {m}}.}$

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,2^e éd. (ISBN 0471117099), utilise une boucle while pour exécuter tout le travail nécessaire au calcul de l'exponentiation modulaire.

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 ${\displaystyle b^{2^{i}}\ {\pmod {m}}}$, 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 exp₀).

La première ligne de code réalise simplement la multiplication dans ${\displaystyle \prod _{i=0}^{n-1}\left(b^{2^{i}}\right)^{a_{i}}\ {\pmod {m}}}$. Si a_i vaut zéro, le code n'est pas exécuté, ce qui équivaut à multiplier le total par un. Si par contre a_i vaut un, le résultat est simplement multiplié par la variable base (contenant la valeur ${\displaystyle b^{2^{i}}\ {\pmod {m}}}$ de la base originale).

Pour finir, testons avec l'exemple b = 4, e = 13, et m = 497. Comme e est égal à 1101 en binaire et donc d'une longueur de quatre chiffres binaires, la boucle ne s'exécutera que quatre fois :

• Au moment d'entrer 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 remplacé par (1 × 4) mod 497, c'est-à-dire 4. exp est ensuite tronqué à droite et devient 110 (binaire), et base élevée au carré pour valoir (4 × 4) mod 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 et devient 11 (binaire), et base est élevée au carré pour valoir (16 × 16) mod 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 remplacé par (4 × 256) mod 497, c'est-à-dire 30. exp est ensuite tronqué à droite et devient 1, et base est élevée au carré pour valoir (256 × 256) mod 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 remplacé par (30 × 429) mod 497, c'est-à-dire 445. exp est ensuite tronqué à droite et devient 0, et base est élevée au carré pour valoir (429 × 429) mod 497, c'est-à-dire 151. (On remarque que cette dernière multiplication base * base est systématiquement inutile puisque le résultat recherché, ici 445, est déjà connu.)

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.

• Portail de la cryptologie
• Portail de l'informatique théorique