Diverses opérations en cryptographie nécessitent de calculer un multiple ou une puissance : il s'agit par exemple, on le verra, de la manière de chiffrer et déchiffrer pour le RSA, et un générateur de nombres pseudo-aléatoires cryptographiquement sûr tel que le BBS se résume à itérer un calcul de puissance modulo $p$. Ces opérations doivent donc pouvoir se faire efficacement, et ce d'autant plus que les objets considérés ici (les capteurs sans fil) sont peu puissants et sur batterie.
Aussi, étant donné un exposant $e$, on souhaite ici calculer le plus efficacement possible $x^e, \forall x$, c'est-à-dire en minimisant le nombre de multiplications, pour gagner en temps d'exécution.
En effet, pour calculer $X^8$, on peut :
L'écart se creuse très rapidement, entre la méthode naïve et les méthodes plus évoluées. Ainsi, pour calculer $X^{1024}$, il faut
Quand on sait que pour chiffrer, dans la méthode RSA, il faut élever notre message (un nombre) à la puissance "un grand nombre premier" (comprendre : un exposant de plusieurs centaines de chiffres), on comprend l'intérêt de racourcir le temps de calcul d'une puissance.
L'exponentiation rapide est une technique classique, utilisée en pratique, pour obtenir la puissance d'un nombre donné.
Cette exponentiation rapide itère, pour le calcul de $X^e$, les opérations suivantes :
dans un ordre dépendant de l'écriture en base 2 de $e$.
Elle se comprend bien dans sa version récursive :
La technique ci-dessus étant récursive, son implémentation dans un capteur risque d'être problématique. Mais comme les opérations à faire sont déterminées par la parité du nombre suite à une division par 2, ou a une division par 2 après une suppression de 1, on en déduit donc que l'écriture binaire du nombre contient exactement les opérations à faire.
Plus précisément...
15 s'écrit 1111 en base 2.
L'algorithme précédent aboutit au mot $SXSXSX$. Les étapes du calcul sont alors :
| res = $X$ | $X$ | |
| S | res = res * res | $X^2$ |
| X | res = res * $X$ | $X^3$ |
| S | res = res * res | $X^6$ |
| X | res = res * $X$ | $X^7$ |
| S | res = res * res | $X^{14}$ |
| X | res = res * $X$ | $X^{15}$ |
Le dernier résultat (res) contient donc la puissance recherchée, en seulement 6 opérations (contre 14, dans la méthode naïve).
La liste d'exposants est ici : 1, 2, 3, 6, 7, 14, 15.
19 s'écrit 10011 en base 2, ce qui fournit le mot $SSSXSX$.
Après travail, la liste d'exposants est ici : 1, 2, 4, 8, 9, 18, 19.
On pourrait donc calculer $X^{19}$ en 6 multiplications.
Réalisez une fonction qui réalise l'exponentiation rapide dans une pyboard.
Notons pour finir que l'exponentiation rapide ne donne pas la méthode la plus rapide systématiquement. Par exemple, pour calculer $X^{15}$, on aurait pu procéder ainsi :
| $a_1 = X$ | $X$ |
| $a_2 = a_1*a_1$ | $X^2$ |
| $a_3 = a_2*a_1$ | $X^3$ |
| $a_4 = a_3*a_3$ | $X^6$ |
| $a_5 = a_4*a_3$ | $X^9$ |
| $a_6 = a_4*a_4$ | $X^{15}$ |
Soit 5 multiplications pour $X^{15}$, au lieu de 6 par la méthode dite exponentiation rapide. Une meilleure liste d'exposants pour $X^{15}$ est donc : 1, 2, 3, 6, 9, 15. Des techniques plus performantes existent donc, telles que les chaînes d'addition détaillées sur une autre page de ce wiki.