ArithmétiqueNotion · Glossaire
Exponentiation rapide
L'exponentiation rapide est un algorithme efficace pour calculer la puissance a^n d'un nombre ou d'une matrice en utilisant la représentation binaire de n. L'idée est de décomposer la puissance en utilisant la relation a^(2k) = (a^k)², ce qui permet de calculer a^n avec seulement O(log n) multiplications au lieu de n-1. Cet algorithme est fondamental en cryptographie (pour le chiffrement RSA et les tests de primalité probabilistes) et en arithmétique modulaire.
Sommaire
Ce que vous allez apprendre
- Relier l’écriture binaire d’un exposant aux puissances sélectionnées.
- Recalculer 3¹³ avec cinq multiplications.
- Distinguer puissance exacte et exponentiation modulaire rapide.
- Identifier les précautions pour l’exposant nul, l’inverse, les matrices et le débordement.
En clair
Pour obtenir 313, multiplier treize fois le nombre 3 serait inutilement long. On fabrique plutôt les puissances 3, 9, 81 et 6 561 en élevant chaque résultat au carré. Comme 13 vaut 8 + 4 + 1, il suffit ensuite de combiner 38, 34 et 3.
L’exposant écrit en binaire indique précisément les puissances à conserver. À chaque chiffre binaire, l’algorithme effectue au plus une mise au carré et une multiplication supplémentaire. Le nombre d’opérations augmente donc beaucoup moins vite que l’exposant.
Définition
L’exponentiation rapide, aussi appelée exponentiation par carrés successifs, calcule une puissance à exposant entier naturel en exploitant les chiffres binaires de cet exposant. La base est notée a et l’exposant non négatif est noté n. Si n est pair, on divise l’exposant par deux et on élève la base au carré. Si n est impair, on conserve en plus un facteur égal à la base. Les identités utilisées sont et , où k est un entier naturel.
Pour n ≥ 1, et asymptotiquement lorsque n grandit, la méthode demande un nombre de multiplications de l’ordre de log 2(n), contre n − 1 pour le produit répété. Elle s’applique aux nombres et, plus généralement, à toute multiplication associative. Pour une matrice, la base doit être carrée afin que ses puissances soient définies. Le cas n = 0 nécessite un élément neutre : 1 pour les nombres et la matrice identité pour les matrices carrées.
En arithmétique modulaire, on réduit chaque résultat modulo un entier positif après chaque multiplication. Les valeurs intermédiaires restent ainsi petites sans changer le reste final. Cette variante intervient notamment dans RSA et dans des tests probabilistes de primalité. Pour un exposant négatif, la même idée exige que la base possède un inverse dans le cadre considéré.
Un exemple, pas à pas
On cherche la valeur exacte de 313. Les données sont la base 3 et l’exposant 13. Une multiplication répétée demanderait douze multiplications.
1. Écrire l’exposant en binaire : . Les chiffres égaux à 1 sélectionnent donc les puissances d’exposants 8, 4 et 1.
2. Former les carrés successifs : 31 = 3, 32 = 9, 34 = 81 et 38 = 6 561. Cette chaîne demande trois mises au carré.
3. Multiplier seulement les puissances sélectionnées : . Deux multiplications assemblent les trois facteurs. La décomposition binaire rend visibles les facteurs retenus.
Le résultat exact est 1 594 323, obtenu en cinq multiplications au total. Pour contrôler le dernier produit, 6 561 × 81 vaut 531 441, puis 531 441 × 3 vaut bien 1 594 323.
En pratique
Pour calculer une grande puissance exacte, on choisit les carrés successifs dès que l’exposant rend le produit répété coûteux. Le gain est observable dans le nombre d’opérations : pour 313, cinq multiplications remplacent les douze du calcul direct.
En cryptographie, les calculs portent souvent sur des puissances modulo un entier. On préfère alors l’exponentiation modulaire rapide : une réduction après chaque produit évite de manipuler l’immense puissance entière avant d’en prendre le reste.
Pour une matrice carrée, élever la matrice à une grande puissance revient à répéter sa multiplication. Les carrés successifs sont préférables au produit linéaire lorsque l’exposant est grand; une méthode spécialisée peut toutefois être plus efficace si la matrice possède une structure particulière.
À ne pas confondre
Exponentiation rapide et exponentiation modulaire rapide. La première calcule une puissance dans le cadre choisi; la seconde réduit chaque produit modulo un entier positif. Pour 313, l’une donne 1 594 323, tandis que l’autre peut chercher seulement son reste modulo 5, égal à 3.
Exponentiation et multiplication. Pour un exposant entier naturel strictement supérieur à 1, une puissance répète une multiplication, mais l’exponentiation rapide est un ordre de calcul, pas une nouvelle opération. Le test est le résultat attendu : 34 vaut 81, alors que 3 × 4 vaut 12.
Limites et pièges
Exposant nul. La boucle ne réalise aucune multiplication et doit renvoyer l’élément neutre. Pour un nombre, le résultat attendu est 1; pour une matrice carrée, c’est la matrice identité. Une initialisation de l’accumulateur à la base produit donc, en général, un résultat erroné dès n = 0.
Exposant négatif. Les seuls carrés successifs ne suffisent pas. Il faut d’abord remplacer la base par son inverse, qui doit exister. Ainsi, une matrice singulière ne peut pas être élevée à la puissance −1; il faut signaler l’absence d’inverse.
Puissance d’une matrice. Le carré d’une matrice n’est pas obtenu en élevant séparément chaque coefficient au carré. Il faut effectuer le produit matriciel de la matrice par elle-même. Confondre ces deux opérations donne généralement des coefficients différents dès l’exposant 2.
Débordement numérique. L’algorithme réduit le nombre d’opérations, pas la taille du résultat exact. Sur un type entier de capacité fixe, un carré intermédiaire peut déborder. Il faut employer des entiers de précision arbitraire ou, si seul un reste est demandé, réduire modulo l’entier choisi après chaque produit.
Pour aller plus loin
algorithme — Pour situer les étapes finies et non ambiguës qui transforment les données d’entrée en résultat.
arithmétique modulaire — Pour approfondir les réductions qui gardent les intermédiaires petits tout en préservant le reste final.
cryptographie — Pour replacer les grandes puissances modulaires dans la protection et la transmission de l’information.
De Sissa à RSA — Pour suivre un parcours éditorial reliant la croissance des puissances à leur emploi dans RSA.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres