Exponentiation by Squaring (Square-and-Multiply, Binary Exponentiation)

Basic principle

The core idea is simple: express the exponent in binary and scan its bits. Each step squares the running value; when a scanned bit equals 1 the algorithm multiplies by the base. This way a^e is built from successive squarings and occasional multiplications instead of e multiplications. For an overview see exponentiation by squaring.

1. Write the exponent e in binary (for example 13 = 1101).
2. Initialize result = 1 and set current = base a.
3. For each bit of e from least significant to most (or vice versa): square current; if bit = 1 multiply result by current.
4. Return result, which equals a^e (with reductions applied when working modulo n).

A concrete small example: computing a^13 uses about log2(13) squarings and only a few multiplies corresponding to the 1 bits of 13.

Performance and variants

The method performs O(log e) multiplications and squarings, so its cost grows logarithmically with the exponent. Implementations vary: left-to-right or right-to-left bit scanning, recursive or iterative forms, and windowed or sliding-window variants that trade extra precomputation for fewer multiplications. A common application is modular exponentiation, where intermediate values are reduced by a modulus to control size; see modular arithmetic.

Because it works for any associative multiplication, exponentiation by squaring extends to integers, matrices, group elements, and polynomials. It speeds up many algorithms and is a fundamental tool in computer algebra and cryptographic protocols that require fast power computations.

History and notable facts

Forms of the method appear in early mathematical texts. A historical source often cited is the Sanskrit Chandah-sûtra, and versions of the technique reappear across cultures. The algorithm contrasts sharply with naive repeated multiplication and is especially effective when combined with modular reduction or precomputation techniques described in algorithmic literature such as large integer powers.

In practice, implementers choose a variant based on available memory, whether exponent bits are naturally scanned left-to-right, and whether powering is done in a ring, field, or group. These choices affect speed, side-channel resistance, and suitability for constrained environments.