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  est de multiplier  par lui-même  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  mais de l'ordre de .

Par exemple, si l'on écrit en base 2  pour , on constate que
.

Il faut ainsi  opérations pour calculer tous les , puis  opérations supplémentaires pour former le produit des . Le nombre total d'opérations est donc , qui est bien de l'ordre du logarithme de . Cette simple remarque algébrique conduit à l'algorithme présenté dans la section suivante.

Algorithme 

Soit  un entier strictement supérieur à , supposons que l'on sache calculer, pour chaque réel , toutes les puissances  de , pour tout , tel que .
Si  est pair alors . Il suffit alors de calculer  pour .
Si  est impair et , alors . Il suffit de calculer  pour  et de multiplier le résultat par .

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

En comparant à la méthode ordinaire qui consiste à multiplier  par lui-même  fois, cet algorithme nécessite de l'ordre de  multiplications et ainsi accélère le calcul de  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 . 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 : . 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 .

Voir aussi

Articles connexes
 Suite de Fibonacci
 Exponentiation modulaire

Liens externes
 Implémentation dans divers langages de programmation, sur rosettacode.org
 Nombre exact de multiplications avec cet algorithme : 

Algorithme
Exponentielle