Exponentiation by squaring

In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add.

The method is based on the observation that, for a positive integer n, we have

This may be easily implemented as the following recursive algorithm:

Although not tail-recursive, this algorithm may be rewritten into a tail recursive algorithm by introducing an auxiliary function:

The iterative version of the algorithm also uses a bounded auxiliary space, and is given by

A brief analysis shows that such an algorithm uses ${\displaystyle \lfloor \log _{2}n\rfloor }$ squarings and at most ${\displaystyle \lfloor \log _{2}n\rfloor }$ multiplications, where ${\displaystyle \lfloor \;\rfloor }$ denotes the floor function. More precisely, the number of multiplications is one less than the number of ones present in the binary expansion of n. For n greater than about 4 this is computationally more efficient than naively multiplying the base with itself repeatedly.

...
Wikipedia