Binary Exponentiation Algorithm Tutorial

Fast Exponentiation (Binary Exponentiation)

Binary Exponentiation, also known as exponentiation by squaring or fast power, computes $x^n$ in $O(\log n)$ time instead of $O(n)$. You use the property that $x^n = (x^{n/2})^2$ when $n$ is even.

If you compute $x^n$ naively, you need $n$ multiplications. For $n = 10^9$, this won't finish in time. You repeatedly halve the exponent to achieve logarithmic complexity.

function power(x, n, mod):
    result = 1
    x = x mod mod

    while n > 0:
        if n is odd:
            result = (result * x) mod mod
        x = (x * x) mod mod
        n = n / 2 (integer division)

    return result

Example trace: $3^{13} \mod 1000$ $1.$ $n = 13$ (odd): $result = 3$, $x = 9$, $n = 6$ $2.$ $n = 6$ (even): $x = 81$, $n = 3$ $3.$ $n = 3$ (odd): $result = 243$, $x = 561$, $n = 1$ $4.$ $n = 1$ (odd): $result = 594$, done

Applications: You use binary exponentiation for modular arithmetic, matrix exponentiation, cryptography (RSA), and computing large Fibonacci numbers.

Time complexity: $O(\log n)$ multiplications.

Space complexity: $O(1)$ for iterative version.