Binary Exponentiation (Fast Power)

Introduction: The Trillion-Step Problem

Suppose you need to calculate $3^{1,000,000,000,000}$ (3 to the power of 1 trillion).

• Naive Loop: Multiply 3 * 3 * 3... one trillion times. This takes forever.
• Binary Exponentiation: Calculate it in about 40 steps.

This algorithm is the cornerstone of modern cryptography (RSA, Diffie-Hellman), where calculating powers of massive numbers modulo a prime is the standard operation.

What Problem does it solve?

• Input: Base $a$, Exponent $n$, and usually a Modulo $m$.
• Output: $(a^n) \% m$.
• The Promise: Calculates the result in $O(\log n)$ multiplications instead of $O(n)$.

Core Idea (Intuition)

Use the binary representation of the exponent. $3^{10} = 3^{(1010)_2} = 3^8 \cdot 3^2$. Instead of multiplying 3 ten times, we can:

1. Calculate $3^1 = 3$.
2. Square it to get $3^2 = 9$.
3. Square it to get $3^4 = 81$.
4. Square it to get $3^8 = 6561$.
5. Combine the parts we need ($3^8$ and $3^2$) based on the binary bits of 10.

How it Works

1. Initialize result = 1.
2. While $n > 0$:
   • If $n$ is odd (last bit is 1), multiply result by current base $a$.
   • Square the base ($a = a \cdot a$).
   • Divide $n$ by 2 (shift right).

Typical Business Scenarios

• ✅ Cryptography: RSA encryption requires calculating $C = M^e \pmod N$ where $e$ is huge.
• ✅ Matrix Powers: Calculating the $n$-th Fibonacci number in $O(\log n)$ by using matrix exponentiation.
• ✅ Combinatorics: Calculating Modular Inverse ($a^{p-2} \pmod p$) for combinations ${n \choose k}$.

Code Demo (TypeScript)

function modPow(base: bigint, exp: bigint, mod: bigint): bigint {
    let result = 1n;
    base = base % mod;

    while (exp > 0n) {
        // If exp is odd, multiply base with result
        if (exp % 2n === 1n) {
            result = (result * base) % mod;
        }
        // Square the base
        base = (base * base) % mod;
        // Divide exp by 2
        exp = exp / 2n;
    }
    return result;
}

Performance & Complexity

• Time: $O(\log n)$.
• Space: $O(1)$.

Summary

“Binary Exponentiation is the art of doubling. By squaring the base repeatedly, it traverses the exponent exponentially fast, turning impossible calculations into instant ones.”