Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Exponentiation rapide

L'algorithme d'exponentiation rapide est utilisé pour calculer rapidement de grandes puissances d'un nombre donné x.

Algorithme

Soit n un entier strictement supérieur à 1, supposons que l'on sache calculer pour tout 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 avec y=x².
• Si n est impair et n>1, alors xⁿ=x×(x²)^(n-1)/2. Il suffit de calculer y^(n-1)/2 avec y=x² et de multiplier par x le résultat.

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

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(lg 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))^-1.

Exemple d'implémentation

Voici une implémentation de l'algorithme précédent dans le langage de programmation Ruby. Il n'utilise pas la récursivité, ce qui augmente la vitesse d'exécution également. Dans la plupart des langages vous aurez besoin de remplacer resultat=1 par resultat=matrice_unite_de_la_meme_taille_que_x pour obtenir le programme de calcul d'une puissance d'une matrice. En Ruby, resultat s'adapte automatiquement au type approprié, ainsi cette fonction s'utilise aussi bien avec les matrices qu'avec les entiers ou les réels.

def puissance(x,n)
 resultat = 1
 while (n != 0)
 # si n est impair, on multiplie resultat par x
 if ((n % 2) == 1) then
 resultat = resultat * x
 end
 x = x*x
 n = n/2
 end
 return resultat
end

Voir aussi

• Suite de Fibonacci
• Exponentiation modulaire