No history yet

Modular Exponentiation

Fast Exponentiation

Calculating powers can be slow. If you need to find ab(modm)a^b \pmod m, a simple loop that multiplies aa by itself bb times is too inefficient when bb is large, like 101810^{18}. This would take far too long to compute. We need a faster way.

The solution is a technique called binary exponentiation, also known as exponentiation by squaring. The core idea might feel familiar if you've worked with binary lifting for finding the Lowest Common Ancestor in trees. In both cases, we leverage powers of two to make huge leaps instead of taking small steps.

Instead of multiplying bb times, we can compute aba^b in just O(log⁡b)O(\log b) multiplications.

The insight is to use the binary representation of the exponent bb. Any integer can be written as a sum of powers of two. For example, the number 13 in binary is 1101, which corresponds to:

13=8+4+0+1=23+22+2013 = 8 + 4 + 0 + 1 = 2^3 + 2^2 + 2^0

Using this, we can rewrite a13a^{13}:

a13=a8+4+1=a8⋅a4⋅a1a^{13} = a^{8+4+1} = a^8 \cdot a^4 \cdot a^1

This is a big improvement because we can find the terms a1,a2,a4,a8,…a^1, a^2, a^4, a^8, \dots very quickly. Each term is just the square of the one before it, all calculated modulo mm:

a1≡a(modm)a2≡(a1)2(modm)a4≡(a2)2(modm)a8≡(a4)2(modm)⋮\begin{aligned} a^1 &\equiv a \pmod m \\ a^2 &\equiv (a^1)^2 \pmod m \\ a^4 &\equiv (a^2)^2 \pmod m \\ a^8 &\equiv (a^4)^2 \pmod m \\ &\vdots \end{aligned}

So, the algorithm has two parts: first, generate the powers of aa by squaring. Second, multiply the ones that correspond to the '1' bits in the binary representation of bb.

Iterative Implementation

We can implement this efficiently with a while loop. The loop continues as long as the exponent b is greater than 0. In each step, we check if the last bit of b is a 1. If it is, we multiply our current result by the current power of aa. Then, we square aa and right-shift b by one bit (which is the same as integer dividing by 2).

long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        // If b is odd, multiply a with result
        if (b & 1) {
            res = (res * a) % m;
        }
        // a becomes a^2, a^4, a^8, ...
        a = (a * a) % m;
        // b is shifted to the right (divided by 2)
        b >>= 1;
    }
    return res;
}

Let's trace binpow(3, 13, 100):

  1. res = 1, a = 3, b = 13 (binary 1101). b is odd, so res = (1 * 3) % 100 = 3. Then a = (3 * 3) % 100 = 9, b = 6.
  2. res = 3, a = 9, b = 6 (binary 110). b is even. Then a = (9 * 9) % 100 = 81, b = 3.
  3. res = 3, a = 81, b = 3 (binary 11). b is odd, so res = (3 * 81) % 100 = 243 % 100 = 43. Then a = (81 * 81) % 100 = 6561 % 100 = 61, b = 1.
  4. res = 43, a = 61, b = 1 (binary 1). b is odd, so res = (43 * 61) % 100 = 2623 % 100 = 23. Then a = (61 * 61) % 100 = 3721 % 100 = 21, b = 0.
  5. b is 0, the loop terminates. The function returns 23.

Binary exponentiation (also known as exponentiation by squaring) is a trick which allows to calculate ana^n using only O(log⁡n)O(\log n) multiplications (instead of O(n)O(n) multiplications required by the naive approach).

Recursive Approach

Binary exponentiation can also be framed recursively. The logic is based on a simple observation:

  • If bb is even, then ab=(ab/2)2a^b = (a^{b/2})^2.
  • If bb is odd, then ab=a⋅ab−1=a⋅(a(b−1)/2)2a^b = a \cdot a^{b-1} = a \cdot (a^{(b-1)/2})^2.

This gives us a clear recursive structure. We solve the problem for b/2b/2 and use that result to find the answer for bb.

long long binpow_recursive(long long a, long long b, long long m) {
    if (b == 0) {
        return 1;
    }
    long long res = binpow_recursive(a, b / 2, m);
    res = (res * res) % m;
    if (b % 2 == 1) { // If b is odd
        res = (res * a) % m;
    }
    return res;
}

Both the iterative and recursive versions have a time complexity of O(log⁡b)O(\log b) because they halve the exponent in each step. The iterative version is often preferred in competitive programming as it avoids the overhead of function calls and the risk of stack overflow for very large recursion depths, though that's rarely an issue for this algorithm.

Quiz Questions 1/5

What is the primary advantage of using binary exponentiation to calculate ab(modm)a^b \pmod m compared to a simple loop that multiplies aa by itself bb times?

Quiz Questions 2/5

The core idea of binary exponentiation is to leverage the binary representation of the exponent. If you are calculating a22a^{22}, and the binary representation of 22 is 10110, which powers of aa will be multiplied together to get the final result?

With this technique, you can now handle calculations involving enormous exponents efficiently, a common requirement in number theory and cryptography problems.