Modular Exponentiation & Fast Exponentiation

Number Theory & Cryptographic Math

Chapter 7 · Modular Exponentiation & Fast Exponentiation

Chapter 6's code quietly used Python's built-in three-argument pow(a, b, n) without explaining how it computes aᵇ mod n so fast even when b is astronomically large. This chapter opens that box — and the answer turns out to be a direct, concrete payoff of Algorithms & Complexity's own recursion and growth-rate machinery.

The Naive Approach, and Why It Can't Scale

The obvious way to compute aᵇ mod n: multiply by a, one step at a time, b times, reducing mod n along the way. That's O(b) multiplications — linear in the exponent itself, not the number of digits in the exponent.

Why this genuinely can't work at RSA scale

A real 2048-bit RSA exponent can be a number with roughly 617 decimal digits. The naive approach needs a number of multiplications equal to that exponent's own value — not its digit count. That's not "slow," it's a number of operations vastly larger than the number of atoms in the observable universe.

Fast Exponentiation: Square-and-Multiply

The fix reuses the exact same halving idea behind Algorithms & Complexity's own T(n) = T(n/2) + O(1) recurrence: aᵇ can always be built from a^(b/2), squared — halving the exponent at every step instead of decrementing it by one.

The recursive idea

If b is even: aᵇ = (a^(b/2))². If b is odd: aᵇ = a × (a^((b−1)/2))². Either way, the exponent roughly halves every step — O(log b) multiplications total, exactly Algorithms & Complexity's own logarithmic-recursion shape.

In practice, this is implemented iteratively by walking through b's own binary digits — squaring a running base value at every step, and multiplying it into the running result exactly when the current bit is 1.

Traced and verified directly — 3¹³ mod 7 (13 = 1101 in binary)

bit=1: result = 1×3 mod 7 = 3, square base: 3² mod 7 = 2
bit=0: (no multiply), square base: 2² mod 7 = 4
bit=1: result = 3×4 mod 7 = 5, square base: 4² mod 7 = 2
bit=1: result = 5×2 mod 7 = 3, square base: 2² mod 7 = 4
Final result: 3 — matching the naive method's own 3¹³ mod 7 result exactly, computed in 7 total multiplications (4 squarings + 3 bit-multiplies) instead of the naive method's 13.

The Gap, at Real Scale

Exponent b	Naive: O(b) multiplications	Fast: O(log b) multiplications
13	13	7
100	100	10
1,000	1,000	16
2²⁰⁴⁸ (real 2048-bit RSA scale, 617 digits)	~10⁶¹⁷ — physically impossible	2,050

All values verified directly. At real RSA scale (b = 2²⁰⁴⁸, a number with a single bit set among its 2,049 binary digits), fast exponentiation needs one squaring per bit position plus one extra multiply for that single set bit — 2,049 + 1 = 2,050 total, matching the verified count exactly. A computation any modern computer finishes in milliseconds, for a naive approach that would never finish at all.

The Other Half of the Trick: Reduce After Every Multiplication

Fast exponentiation alone isn't enough — Chapter 3's own reduce-anytime property has to be applied at every single step, not just at the end, or the raw numbers explode before the exponent ever finishes shrinking.

Verified directly — the digit-length explosion, with and without reducing every step

Repeatedly squaring 3 without ever reducing: 1, 2, 4, 8, 16, 31 digits after each successive squaring — doubling every step. After just 11 squarings, the raw unreduced number has 978 digits. Reducing mod n after every single squaring, the value never exceeds n's own digit count — 9 digits, the entire way through, no matter how many squarings run.

Real Relevance: This Is Literally How RSA Encrypts and Decrypts

Chapter 9 defines RSA encryption as c = mᵉ mod n and decryption as m = cᵈ mod n — both are modular exponentiations, computed with the exact algorithm in this chapter, on numbers hundreds of digits long. Fast exponentiation isn't an optimization RSA happens to use — it's the specific reason RSA is fast enough to be usable at all.

Fast Modular Exponentiation in Code

def fast_modpow(a, b, n):
    result = 1
    base = a % n
    while b > 0:
        if b & 1:                        # current bit is 1
            result = (result * base) % n
        base = (base * base) % n     # reduce EVERY step -- Chapter 3
        b >>= 1                            # move to the next bit
    return result

print(fast_modpow(3, 13, 7))              # 3
print(fast_modpow(3, 13, 7) == pow(3, 13, 7))  # True -- matches Python's own built-in

Hands-On Exercises

Exercise 1

Using the square-and-multiply method, trace 5⁹ mod 11 step by step (write out 9 in binary first). Show each squaring and each bit-triggered multiply, and state the final result and total multiplication count.

📄 View solution

Exercise 2

For an exponent b = 10,000, compute how many multiplications the naive approach needs, and roughly how many the fast approach needs (using log₂(b)). Compute the ratio between them.

📄 View solution

Exercise 3

Explain, using this chapter's own digit-length findings, why a fast exponentiation implementation that forgets to reduce mod n after every squaring (and only reduces once at the very end) would still be dramatically slower than the correct version — even though it uses the exact same O(log b) number of multiplications.

📄 View solution

Chapter 7 Quick Reference

Naive exponentiation: O(b) multiplications — infeasible for RSA-scale exponents
Fast exponentiation (square-and-multiply): O(log b) multiplications — walks the exponent's own binary digits
Verified at 2048-bit RSA scale: 2,050 multiplications, vs. a physically impossible ~10⁶¹⁷ for the naive approach
Reduce mod n after every single multiplication — not just at the end — or the raw numbers double in digit-length every step
This is the exact algorithm behind RSA's own c = mᵉ mod n encryption and m = cᵈ mod n decryption (Chapter 9)
Next chapter: Euler's totient function and Fermat's Little Theorem