Exponentiation rapide...

Lorsque l'on souhaite calculer aⁿ, on peut naïvement effectuer n-1 multiplications en faisant :

Cependant, l'exemple suivant montre que l'on peut calculer a²⁰⁴⁸ en effectuant simplement 11 multiplication (chaque fois que l'on élève au carré) : 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ⁿ=1.
• si n=2p est pair, alors aⁿ=(a^p)².
• si n=2p+1 est impair, alors aⁿ=(a^p)²×a.

Alors que l'algorithme naïf demande de l'ordre de n multiplications pour calculer aⁿ, l'algorithme d'exponentiation rapide se contente de l'ordre de ln(n) multiplications. En outre, tester si un entier est pair est très rapide sur un ordinateur.