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[modifier | modifier le code]

La première façon de calculer une puissance $x n$ 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, $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 $d$ opérations pour calculer tous les $x^{2^{k}}$ , puis $d$ opérations supplémentaires pour former le produit des $(x^{2^{k}})^{a_{k}}$ . Le nombre total d'opérations est donc $2 d$ , 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[modifier | modifier le code]

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 \leq k < n$ .

Si $n$ est pair alors $x n = (x 2) n /2$ . Il suffit alors de calculer $y n /2$ pour $y = x 2$ .
Si $n$ est impair et $n > 1$ , alors $x n = x (x 2) (n - 1)/2$ . Il suffit de calculer $y (n - 1)/2$ pour $y = x 2$ et de multiplier le résultat par $x$ .

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

{\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 n$ 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)) -1$ . 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[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]