Square-and-multiply algorithm

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 method uses the bits of the exponent to determine which powers are computed.

This example shows how to compute ${\displaystyle x^{13}}$ using this method. The exponent, 13, is 1101 in binary. The bits are used in left to right order. The exponent has 4 bits, so there are 4 iterations.

First, initialize the result to 1: ${\displaystyle r\leftarrow 1\,(=x^{0})}$.

...
Wikipedia