Le coût réel des grands entiers

Bien que l'algorithme n'effectue que $O(\log n)$ multiplications, la taille des entiers manipulés double à chaque étape. Les dernières multiplications portent sur des entiers géants ayant jusqu'à $n$ bits de stockage. La complexité d'une multiplication de taille $d$ n'est pas en $O(1)$ mais croît au moins de façon linéaire en $O(d)$. La complexité totale de l'exponentiation est donc dominée par la dernière multiplication de taille $n$, rendant le coût global linéaire ou supra-linéaire en fonction de la taille finale.