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, en base 2, pour . Donc, .
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 :
Catégorie:Algorithme Catégorie:Exponentielle