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 xⁿ est de multiplier x par lui-même n 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 n mais de l'ordre de ln(n).

Par exemple, en base 2, ${\displaystyle n=\sum _{k=0}^{d}a_{k}2^{k}}$ pour ${\displaystyle a_{k}\in \{0,1\}}$. Donc,

${\displaystyle x^{n}=x^{a_{0}}(x^{2})^{a_{1}}(x^{2^{2}})^{a_{2}}\dots (x^{2^{d}})^{a_{d}}}$.

Il faut ainsi d opérations pour calculer tous les ${\displaystyle x^{2^{k}}}$, puis d opérations supplémentaires pour former le produit des ${\displaystyle (x^{2^{k}})^{a_{k}}}$. Le nombre total d'opérations est donc 2d, qui est bien de l'ordre du logarithme de n. Cette simple remarque algébrique conduit à l'algorithme présenté dans la section suivante.

Algorithme

Soit n un entier strictement supérieur à 1, supposons que l'on sache calculer, pour chaque réel x, toutes les puissances x^k de x, pour tout k, tel que 1 ≤ k < n.

• Si n est pair alors xⁿ = (x²)^n/2. Il suffit alors de calculer y^n/2 pour y = x².
• Si n est impair et n > 1, alors xⁿ = x(x²)^{(n – 1)/2}. Il suffit de calculer y^{(n – 1)/2} pour y = x² et de multiplier le résultat par x.

Cette remarque nous amène à l'algorithme récursif suivant qui calcule xⁿ pour un entier strictement positif n :

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

En comparant à la méthode ordinaire qui consiste à multiplier x par lui-même n – 1 fois, cet algorithme nécessite de l'ordre de O(log n) multiplications et ainsi accélère le calcul de xⁿ 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 q. 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 : puissance(x, –n) = (puissance(x, n))⁻¹. 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 ${\displaystyle (\mathbb {Z} ,+)}$.

Voir aussi

Articles connexes

• Suite de Fibonacci
• Exponentiation modulaire

Liens externes

• (en) Implémentation dans divers langages de programmation, sur rosettacode.org
• (en) Nombre exact de multiplications avec cet algorithme : suite A014701 de l'OEIS

• Portail de l'informatique théorique
• Arithmétique et théorie des nombres