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, en base 2, $n=\sum _{k=0}^d{a}_k{2}^k$ pour $a_k\in \{0,1\}$. Donc,

$x^n=x^{a_0}(x^2{)}^{a_1}(x^{2^2}{)}^{a_2}\dots (x^{2^d}{)}^{a_d}$.

Il faut ainsi Modèle:Mvar opérations pour calculer tous les $x^{2^k}$, puis Modèle:Mvar opérations supplémentaires pour former le produit des $(x^{2^k}{)}^{a_k}$. 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 :

$\text{puissance}(x,n)=\{\begin{array}{cc}x,& \text{si }n\text{ = 1}\\ \text{puissance}(x^2,n/2),& \text{si }n\text{ est pair}\\ x\times \text{puissance}(x^2,(n-1)/2),& \text{si }n\text{ est impair}\end{array}$

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 $(\mathbb{Z},+)$.

Voir aussi

Articles connexes

• Suite de Fibonacci
• Exponentiation modulaire

Liens externes

• Modèle:En Implémentation dans divers langages de programmation, sur rosettacode.org
• Modèle:En Nombre exact de multiplications avec cet algorithme : Modèle:OEIS