Case Study: Building and Verifying Fast Exponentiation

"A program is correct when you can explain why it works — to a skeptic."

Executive Summary

In this build-focused case study you'll write three versions of "raise b to the power e" — a naive loop, a recursive version, and the clever exponentiation by squaring that does it in $O(\log e)$ steps — and you'll prove each one correct by induction as you go. The fast version is the engine behind RSA (Chapter 25): real cryptographic keys raise huge numbers to huge exponents, and the naive method would take longer than the age of the universe. By the end you'll have the first serious piece of the Toolkit's number-theory machinery, and a proof that it computes what it claims.

Skills applied

  • Building functions incrementally and stating the correctness claim for each.
  • Proving a recursive function correct by induction (and seeing where ordinary induction needs help).
  • Using check_identity to test before you prove.
  • Connecting an inductive correctness argument to a real performance win.

Background: why ** isn't the end of the story

Python has b ** e. So why build our own? Two reasons. First, understanding: the algorithm inside ** is a beautiful, short induction you should be able to reproduce. Second, generalization: in Chapter 23 we'll need pow(b, e, m) — exponentiation modulo m — where you cannot just compute the gigantic b ** e and then reduce, because b ** e may have millions of digits. The fast, square-as-you-go structure you build here is exactly what survives that generalization. So we build it now, prove it now, and reuse it for crypto later.

🔗 Connection: This case study is the first stop on the book's RSA thread (see also Chapters 15, 22, 23, 24, and the implementation in 25). Everything you prove here about integer exponentiation carries over, almost verbatim, to modular exponentiation.

Phase 1: The naive version (and its invariant)

Start simple: multiply b into an accumulator e times.

def power_naive(b, e):
    """Return b**e for integer e >= 0, by repeated multiplication."""
    result = 1
    count = 0
    while count < e:
        result = result * b
        count = count + 1
    return result

print(power_naive(3, 4))
# Expected output:
# 81

Claim. power_naive(b, e) returns $b^e$ for every integer $e \ge 0$.

Invariant. At the top of the loop test, $\text{result} = b^{\text{count}}$.

  • Initialization: before the loop, $\text{count} = 0$ and $\text{result} = 1 = b^0$. ✓
  • Maintenance: if $\text{result} = b^{\text{count}}$ and the body runs, it sets $\text{result}' = b^{\text{count}} \cdot b = b^{\text{count}+1}$ and $\text{count}' = \text{count}+1$, so $\text{result}' = b^{\text{count}'}$. ✓
  • Termination: the loop ends with $\text{count} = e$, so $\text{result} = b^e$. $\blacksquare$

This works, but it costs $e$ multiplications. For RSA-sized exponents (hundreds of digits) that is hopeless.

🔄 Check Your Understanding If e has $d$ decimal digits, roughly how many multiplications does power_naive perform? Why does that make it unusable for cryptography?

Answer

About $e \approx 10^d$ multiplications — exponential in the number of digits. A 300-digit exponent means roughly $10^{300}$ multiplications, vastly more than could ever be performed. We need something that scales with the number of digits, not the value.

Phase 2: The recursive version

Rewrite the same idea recursively — this makes the induction proof fall out almost for free.

def power_rec(b, e):
    """Return b**e for integer e >= 0, recursively."""
    if e == 0:
        return 1
    return b * power_rec(b, e - 1)

print(power_rec(3, 4))
# Expected output:
# 81

Claim. power_rec(b, e) returns $b^e$ for all $e \ge 0$.

Proof (induction on $e$). Let $P(e)$ be "power_rec(b, e) returns $b^e$." Base case ($e=0$): the function returns $1 = b^0$. ✓ Inductive step: assume $P(e)$. For input $e+1 \ge 1$, the function returns b * power_rec(b, e), which by the inductive hypothesis is $b \cdot b^{e} = b^{e+1}$. ✓ By induction, correct for all $e \ge 0$. $\blacksquare$

💡 Intuition: Same cost as the naive loop ($e$ multiplications), but notice how the proof shrank. The recursive call is the inductive hypothesis, so the proof has one honest line. This is the §6.4 lesson in action: write code whose structure mirrors the proof you'll need.

Phase 3: Exponentiation by squaring (the fast version)

Here is the key insight, and it's an algebraic identity: $$b^{e} = \begin{cases} \left(b^{e/2}\right)^2 & \text{if } e \text{ is even},\\[2pt] b \cdot \left(b^{(e-1)/2}\right)^2 & \text{if } e \text{ is odd}.\end{cases}$$ Each case halves the exponent. Halving $e$ can only happen about $\log_2 e$ times before reaching 0 — so this computes $b^e$ in $O(\log e)$ multiplications instead of $O(e)$.

def power_fast(b, e):
    """Return b**e for integer e >= 0, in O(log e) multiplications."""
    if e == 0:
        return 1
    half = power_fast(b, e // 2)   # integer division
    if e % 2 == 0:
        return half * half
    return b * half * half

print(power_fast(3, 13))    # 3**13 = 1594323
# Expected output:
# 1594323

Claim. power_fast(b, e) returns $b^e$ for all $e \ge 0$.

The strategy first. The recursive call is on e // 2, not e - 1. So to justify it we must assume the function is correct on $\lfloor e/2 \rfloor$ — which is not the immediately previous case. Ordinary induction ("assume $P(e)$, prove $P(e+1)$") doesn't directly grant that. We need to assume $P(j)$ for all $j < e$. That is strong induction, the subject of Chapter 7. We'll write the proof in the strong-induction form; treat this as a motivated preview.

Proof (strong induction on $e$). Let $P(e)$ be "power_fast(b, e) returns $b^e$." Assume $P(j)$ holds for all $0 \le j < e$; we prove $P(e)$.

  • If $e = 0$: returns $1 = b^0$. ✓ (base case)
  • If $e \ge 1$: the call power_fast(b, e // 2) has argument $\lfloor e/2 \rfloor < e$, so by the strong hypothesis it returns $b^{\lfloor e/2 \rfloor}$; call it $h$.
  • If $e$ is even, $e = 2\lfloor e/2 \rfloor$, and the function returns $h \cdot h = \left(b^{\lfloor e/2\rfloor}\right)^2 = b^{2\lfloor e/2\rfloor} = b^{e}$. ✓
  • If $e$ is odd, $e = 2\lfloor e/2 \rfloor + 1$, and the function returns $b \cdot h \cdot h = b \cdot b^{2\lfloor e/2\rfloor} = b^{2\lfloor e/2\rfloor + 1} = b^{e}$. ✓

By strong induction, power_fast(b, e) is correct for all $e \ge 0$. $\blacksquare$

🚪 Threshold Concept (preview). Notice why ordinary induction wasn't enough: the recursion doesn't step down by one, it halves. Whenever a recursive call jumps to a much smaller (but not immediately previous) case — divide-and-conquer, binary search, mergesort, this — you'll reach for strong induction. Spotting "this recursion isn't $n \to n-1$" is the cue. Chapter 7 makes it precise.

Phase 4: Test, then trust

Before trusting any of this, test it — theme four says computation and proof work together. Use the Toolkit's check_identity (from this chapter's Project Checkpoint) to compare all three functions against Python's built-in ** over a range of exponents:

from dmtoolkit.recurrences import check_identity

b = 7
naive  = lambda e: power_naive(b, e)
fast   = lambda e: power_fast(b, e)
truth  = lambda e: b ** e

print(check_identity(naive, truth, upto=20, start=0))   # compare naive vs **
print(check_identity(fast,  truth, upto=20, start=0))   # compare fast  vs **
# Expected output:
# None
# None

Two Nones: no exponent in $[0, 20]$ made either function disagree with **. That's reassuring evidence — and because we also proved both correct, we know the agreement continues forever. The test catches typos; the proof certifies the algorithm.

⚠️ Common Pitfall: A subtle bug in power_fast — say, returning b * half instead of b * half * half in the odd case — would pass casual eyeballing but fail check_identity almost immediately (try it). And the proof would refuse to go through: the odd-case algebra would no longer equal $b^e$. Both safety nets catch it; together they're hard to fool.

Discussion Questions

  1. The fast version's proof needed strong induction. Could you restructure the recursion (e.g., step e down by 1) to make ordinary induction sufficient? What would you lose?
  2. Exactly how many multiplications does power_fast(b, e) perform, as a function of the number of bits in e? Tie your answer to Chapter 14's notion of $O(\log e)$.
  3. In Chapter 23 we'll add a third argument: power_fast(b, e, m) returning $b^e \bmod m$. Which line changes, and why does reducing mod m after every multiplication keep the numbers small without changing the result?
  4. The naive and recursive versions are correct but slow; the fast one is correct and fast. Argue that "correct" had to come first — what would it mean to optimize a function you couldn't prove correct?

Your Turn: Extensions

  • Option A (toward RSA). Implement power_mod(b, e, m) (fast, reducing mod m each step) and test it against pow(b, e, m) with check_identity. You'll have built the single most important primitive in RSA — keep it; Chapter 23 expects it in numbertheory.py as mod_pow.
  • Option B (iterative fast power). Rewrite power_fast as a loop that scans the bits of e. State its loop invariant and prove it (this is the version most libraries actually use).
  • Option C (count the work). Instrument each function to count multiplications, run them in your head for $e = 1, 2, 4, 8, 16, 1000$, and tabulate naive vs. fast. Confirm the $O(\log e)$ behavior.

Key Takeaways

  1. Build, then verify, incrementally. Each version came with its own one-line correctness claim and a proof matched to its structure.
  2. The recursion's shape dictates the proof. Stepping down by one → ordinary induction; halving → strong induction (Chapter 7). Recognizing the shape tells you which tool you need.
  3. Fast exponentiation is an induction you'll reuse. It is the computational heart of RSA; proving it now means trusting it later.
  4. Test and prove are partners. check_identity catches the typos a proof assumes away; the proof certifies the cases a test can never reach.