Fast Exponentiation

Observation:

$$x^n=\{\begin{array}{ll}x(x^2{)}^{(n-1)/2},& \text{mbox}ifn\text{mbox}isodd\\ (x^2{)}^{n/2},& \text{mbox}ifn\text{mbox}iseven\end{array}$$

Thus we can achieve $O(\log n)$ multiplications.