 Exponentiation by squaring

Repeated squaring computes $a^n$ using $O(\log n)$ multiplications by reading the binary expansion of $n$. Performing every multiplication modulo $m$ computes $a^n\mathrm{mod}m$ with the same number of modular multiplications.

Exponentiation by squaring is an efficient algorithm used to compute powers of a number, particularly useful for large exponents. This method reduces the number of multiplications needed, making it much faster than the naive approach of multiplying the base by itself repeatedly. The basic idea behind exponentiation by squaring is to take advantage of the properties of exponents.