Exponentiation rapide
Lorsque l'on souhaite calculer $a^n$, on peut naïvement effectuer $n-1$ multiplications en effectuant le produit : $$a=a\times a\times a\times \cdots\times a.$$
Cependant, l'exemple suivant montre que l'on peut calculer $a^{2048}$ en effectuant simplement 11 multiplications (chaque fois que l'on élève au carré) : $$a^{2048}=\left(\left(\left(\left(\left(\left(\left(\left(\left(\left(2\right)^2\right)^2\right)^2\right)^2\right)^2\right)^2\right)^2\right)^2\right)^2\right)^2.$$
L'algorithme d'exponentiation rapide est la transposition au cas général de l'exemple précédent. Une version récursive est donnée par :
- si $n=0$, alors $a^n=1$.
- si $n=2p$ est pair, alors $a^n=(a^p)^2$.
- si $n=2p+1$ est impair, alors $a^n=(a^p)^2\times a$.
Alors que l'algorithme naïf demande de l'ordre de $n$ multiplications pour calculer $a^n$, l'algorithme d'exponentiation rapide se contente de l'ordre de $\ln(n)$ multiplications et de l'ordre de $\ln(n)$ tests de parité. En outre, tester la parité d'un entier est une opération très rapide sur un ordinateur.