Exponentiation rapide
En informatique, 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 »).
Écriture mathématique
La première façon de calculer une puissance Modèle:Mvar est de multiplier Modèle:Mvar par lui-même Modèle:Mvar fois. Cependant, il existe des méthodes bien plus efficaces, où le nombre d'opérations nécessaires n'est plus de l'ordre de Modèle:Mvar mais de l'ordre de Modèle:Math.
Par exemple, si l'on écrit en base 2 <math>n=\sum_{k=0}^d a_k2^k</math> pour <math>a_k\in \{0,1\}</math>, on constate que
- <math>x^n=x^{a_0}(x^2)^{a_1}(x^{2^2})^{a_2}\dots (x^{2^d})^{a_d}</math>.
Il faut ainsi Modèle:Mvar opérations pour calculer tous les <math>x^{2^k}</math>, puis Modèle:Mvar opérations supplémentaires pour former le produit des <math>(x^{2^k})^{a_k}</math>. Le nombre total d'opérations est donc Modèle:Math, qui est bien de l'ordre du logarithme de Modèle:Mvar. Cette simple remarque algébrique conduit à l'algorithme présenté dans la section suivante.
Algorithme
Soit Modèle:Mvar un entier strictement supérieur à Modèle:Math, supposons que l'on sache calculer, pour chaque réel Modèle:Mvar, toutes les puissances Modèle:Mvar de Modèle:Mvar, pour tout Modèle:Mvar, tel que Modèle:Math.
- Si Modèle:Mvar est pair alors Modèle:Math. Il suffit alors de calculer Modèle:Math pour Modèle:Math.
- Si Modèle:Mvar est impair et Modèle:Math, alors Modèle:Math. Il suffit de calculer Modèle:Math pour Modèle:Math et de multiplier le résultat par Modèle:Mvar.
Cette remarque nous amène à l'algorithme récursif suivant qui calcule Modèle:Mvar pour un entier strictement positif Modèle:Mvar :
- <math>
\mbox{puissance}(x,\,n)=\left\{ \begin{matrix} x, & \mbox{si }n\mbox{ = 1} \\ \mbox{puissance}(x^2,\,n/2), & \mbox{si }n\mbox{ est pair} \\ x\times\mbox{puissance}(x^2,\,(n-1)/2), & \mbox{si }n\mbox{ est impair} \\ \end{matrix}\right. </math>
En comparant à la méthode ordinaire qui consiste à multiplier Modèle:Mvar par lui-même Modèle:Math fois, cet algorithme nécessite de l'ordre de Modèle:Math multiplications et ainsi accélère le calcul de Modèle:Mvar de façon spectaculaire pour les grands entiers.
La méthode fonctionne dans tout semi-groupe et est souvent utilisée pour calculer des puissances de matrices, et particulièrement en cryptographie, mais aussi pour calculer les puissances dans un anneau d'entiers modulo Modèle:Mvar. Elle peut être aussi utilisée pour calculer des puissances d'un élément dans un groupe, en utilisant pour les puissances négatives la règle : Modèle:Math. C'est cette méthode que l'on applique lorsque l'on effectue la multiplication de deux nombres chiffre par chiffre en base 2 : le groupe est <math>(\Z,+)</math>.
Voir aussi
Articles connexes
Liens externes
- {{#invoke:Langue|indicationDeLangue}} Implémentation dans divers langages de programmation, sur rosettacode.org
- {{#invoke:Langue|indicationDeLangue}} Nombre exact de multiplications avec cet algorithme : Modèle:OEIS
