Modular exponentiation and fast powering

SECTION 1

Historical Context & Motivation

The problem of computing large powers under a modulus has deep historical roots, stretching from classical number theory into the infrastructure of modern digital security. Long before the advent of electronic computers, mathematicians recognized that modular arithmetic — the study of remainders under division — possessed elegant structural properties that could simplify otherwise intractable computations. The challenge was always one of scale: how does one compute b^e mod m when the exponent e is astronomically large, perhaps hundreds of digits long? Naively multiplying b by itself e times is computationally infeasible for the exponents encountered in cryptography, yet the answer — a number no larger than m — is perfectly manageable. This tension between the enormous intermediate computation and the compact final result is precisely what fast powering algorithms resolve.

~200 BCE • Early Modular Arithmetic in China

The Chinese Remainder Theorem appears in Sunzi Suanjing, demonstrating that ancient mathematicians already understood systems of congruences and the power of remainder-based reasoning.

1640 • Fermat's Little Theorem

Pierre de Fermat states that if p is prime and gcd(a, p) = 1, then a^p−1 ≡ 1 (mod p). This foundational result enables modular exponent reduction.

1801 • Gauss's Disquisitiones Arithmeticae

Carl Friedrich Gauss formalizes modular arithmetic with the congruence notation a ≡ b (mod m), systematizing the theory and introducing repeated squaring as a practical technique for exponentiation.

1976–78 • Diffie-Hellman & RSA

Public-key cryptography is born. Both the Diffie-Hellman key exchange and the RSA cryptosystem depend critically on fast modular exponentiation, making it one of the most frequently executed operations in computer science.

Modern Era • Hardware-Accelerated Modular Exponentiation

Dedicated hardware and constant-time algorithms for modular exponentiation protect billions of TLS/SSL connections daily, with Montgomery multiplication and sliding-window methods optimizing the binary method.

The central question that drives this lesson is both simple to state and profound in its implications: given integers b, e, and m, how can we compute b raised to the power e modulo m in time proportional to log e rather than e itself? The answer — the binary method of exponentiation, also known as repeated squaring — transforms an exponential-time procedure into one that is merely logarithmic, and it underpins every modern cryptographic protocol from RSA to elliptic curve Diffie-Hellman.

SECTION 2

Core Principles & Definitions

Before diving into the algorithm, it is essential to establish the foundational ideas that make modular exponentiation both well-defined and computationally tractable. The interplay between the algebraic properties of modular arithmetic and the binary representation of integers is what grants the fast powering algorithm its remarkable efficiency.

Modular Arithmetic

For integers a, b, m, we write a ≡ b (mod m) if m divides (a − b). Arithmetic in ℤ/mℤ preserves addition and multiplication: (a · b) mod m = ((a mod m) · (b mod m)) mod m.

Closure Under Multiplication mod m

Since the product of any two residues modulo m is again a residue modulo m, we never need to store numbers larger than m² during intermediate computations. This property is the key to keeping intermediate results bounded.

Binary Representation of Exponents

Every positive integer e can be expressed as a sum of distinct powers of 2: e = ∑ eᵢ · 2ⁱ where eᵢ ∈ {0, 1}. This decomposition has ⌊log₂ e⌋ + 1 bits and is the structural foundation of repeated squaring.

Repeated Squaring Principle

Since

b^{2k}

= (

b^k

)², each successive power of b raised to a power of 2 can be obtained by squaring the previous one. Combined with the binary decomposition, this reduces e multiplications to at most 2⌊log₂ e⌋ multiplications.

Reduction at Every Step

After each multiplication or squaring, we immediately reduce modulo m. This ensures all operands remain in {0, 1, …, m−1}, preventing exponential blowup of digit sizes and making each arithmetic operation O(log² m).

✦

KEY TAKEAWAY

Think of fast powering like an express elevator versus a staircase. If you need to climb to floor 1000, taking one step at a time requires 1000 steps. But if you can double your height at each stage — floor 1, 2, 4, 8, 16, … — you reach floor 1024 in just 10 jumps. The binary method of exponentiation works the same way: it decomposes the exponent into powers of 2 and combines the corresponding squared values, reducing O(e) multiplications to O(log e).

SECTION 3

Visual Explanation

The following diagram illustrates the repeated squaring process for computing 3^13 mod 17. The exponent 13 in binary is 1101₂ = 8 + 4 + 1. The algorithm builds a table of successive squares of the base modulo 17, then multiplies together only those powers whose corresponding binary digit is 1.

The diagram shows the three phases of the binary method: building a squaring table by repeatedly squaring mod 17, selecting only the entries corresponding to 1-bits in the binary expansion of 13 = 1101₂, and finally multiplying the selected residues together to obtain the result 12.

Observe the dramatic efficiency gain depicted in the diagram. The naive approach would require 12 sequential multiplications (computing 3 × 3 × 3 × … thirteen times), whereas the binary method uses only 4 squarings to build the table and 2 additional multiplications to combine the selected powers — a total of 6 modular multiplications. For cryptographic exponents of 2048 bits, this difference is the gap between feasibility and impossibility: roughly 4000 multiplications via repeated squaring versus 2²⁰⁴⁸ multiplications naively — a number exceeding the atoms in the observable universe.

SECTION 4

Mathematical Framework

We now formalize the algorithm and analyze its complexity. The mathematical elegance of repeated squaring rests on a simple identity from the theory of exponents combined with the multiplicative closure of ℤ/mℤ.

MODULAR EXPONENTIATION PROBLEM

Given b, e, m ∈ ℤ with m > 0 and e ≥ 0, compute r = bᵉ mod m

Here b is the base, e is the exponent, m is the modulus, and r ∈ {0, 1, …, m − 1} is the result.

BINARY DECOMPOSITION

e = eₖ · 2ᵏ + eₖ₋₁ · 2ᵏ⁻¹ + ⋯ + e₁ · 2¹ + e₀ · 2⁰, eᵢ ∈ {0, 1}

The exponent e has k + 1 = ⌊log₂ e⌋ + 1 binary digits. This decomposition means bᵉ = b^eₖ·2ᵏ · b^{eₖ₋₁·2ᵏ⁻¹} · ⋯ · b^e₀·2⁰.

SQUARING RECURRENCE

b^(2^(i+1)) mod m = (b^(2^i) mod m)² mod m

Each successive power of the base raised to a power of 2 is obtained by squaring the previous value and reducing mod m. Since we reduce at every step, all intermediate values lie in {0, …, m − 1}.

COMPLEXITY

T(e, m) = O(log e) modular multiplications, each costing O(log² m) bit operations

The total cost is at most 2⌊log₂ e⌋ modular multiplications (at most ⌊log₂ e⌋ squarings plus at most ⌊log₂ e⌋ multiplications). For an n-bit exponent with an n-bit modulus, the overall bit complexity is O(n³).

💡

Right-to-Left vs. Left-to-Right

The algorithm can be implemented scanning the binary digits of e from least significant to most significant (right-to-left) or from most significant to least significant (left-to-right). The right-to-left version maintains a running product and a running square; the left-to-right version (Horner-style) squares the accumulator and conditionally multiplies by b at each step. Both achieve the same O(log e) complexity.

SECTION 5

Detailed Algorithm & Trace

The right-to-left binary method is perhaps the most intuitive version of the algorithm. It maintains two variables: a running product (initialized to 1) and a running base (initialized to b mod m). At each iteration it inspects the least significant bit of the exponent: if the bit is 1, the running product is multiplied by the running base; then the running base is squared and the exponent is right-shifted by one bit. The loop terminates when the exponent reaches zero.

Flowchart of the right-to-left binary exponentiation algorithm. The green box accumulates the product when a bit is 1, the violet box squares the running base unconditionally, and the pink box halves the exponent (right-shift) at every iteration.

Execution Trace: $7^{327}$ mod 853

Iteration	e (binary)	Bit₀	base mod 853	result mod 853
Init	`101000111`	—	7	1
1	`101000111`	1	49	1 × 7 = 7
2	`10100011`	1	2401 ≡ 816	7 × 49 = 343
3	`1010001`	1	816² mod 853 = 307	343 × 816 mod 853 = 298
4	`101000`	0	307² mod 853 = 462	298 (unchanged)
5	`10100`	0	462² mod 853 = 240	298 (unchanged)
6	`1010`	0	240² mod 853 = 307	298 (unchanged)
7	`101`	1	307² mod 853 = 462	298 × 307 mod 853 = 583
8	`10`	0	462² mod 853 = 240	583 (unchanged)
9	`1`	1	240² mod 853 = 307	583 × 240 mod 853 = 286

Trace of $7^{327}$ mod 853 using right-to-left binary method (327 = 101000111₂)

The trace confirms that 7³²⁷ mod 853 = 286, computed in only 9 iterations (9 squarings + 5 multiplications = 14 total modular multiplications) compared to 326 multiplications using the naive approach. The exponent 327 has 9 binary digits and 5 of them are set to 1, which precisely matches the number of modular multiplications required beyond the squarings.

SECTION 6

Worked Example

Let us work through a complete example that mirrors a simplified RSA encryption scenario. We will compute 5^117 mod 19 using the right-to-left binary method, showing every intermediate step and the corresponding modular reduction.

Computing 5¹¹⁷ mod 19

1
Step 1 — Convert Exponent to Binary

We need 117 in binary. Performing successive division by 2: 117 = 58 × 2 + 1, 58 = 29 × 2 + 0, 29 = 14 × 2 + 1, 14 = 7 × 2 + 0, 7 = 3 × 2 + 1, 3 = 1 × 2 + 1, 1 = 0 × 2 + 1. Reading the remainders from bottom to top gives 1110101₂.

117 = 1110101₂ = 2⁰ + 2² + 2⁴ + 2⁵ + 2⁶ = 1 + 4 + 16 + 32 + 64
2
Step 2 — Build the Squaring Table mod 19

Starting from 5 mod 19 = 5, we repeatedly square and reduce. 5¹ ≡ 5, 5² ≡ 25 ≡ 6, 5⁴ ≡ 6² = 36 ≡ 17, 5⁸ ≡ 17² = 289 ≡ 289 − 15 × 19 = 289 − 285 = 4, 5¹⁶ ≡ 4² = 16, 5³² ≡ 16² = 256 ≡ 256 − 13 × 19 = 256 − 247 = 9, 5⁶⁴ ≡ 9² = 81 ≡ 81 − 4 × 19 = 81 − 76 = 5.

Squaring table: 5¹≡5, 5²≡6, 5⁴≡17, 5⁸≡4, 5¹⁶≡16, 5³²≡9, 5⁶⁴≡5
3
Step 3 — Identify Active Bits

Since 117 = 1110101₂, the 1-bits are at positions 0, 2, 4, 5, and 6. We need to multiply the corresponding entries from our squaring table: 5¹, 5⁴, 5¹⁶, 5³², and 5⁶⁴, i.e., the values 5, 17, 16, 9, and 5 respectively.

Selected values: {5, 17, 16, 9, 5}
4
Step 4 — Multiply Selected Values mod 19

We combine these step by step, reducing mod 19 after each multiplication to keep numbers small. Start with result = 1. Multiply by 5: 1 × 5 = 5. Multiply by 17: 5 × 17 = 85 ≡ 85 − 4 × 19 = 85 − 76 = 9. Multiply by 16: 9 × 16 = 144 ≡ 144 − 7 × 19 = 144 − 133 = 11. Multiply by 9: 11 × 9 = 99 ≡ 99 − 5 × 19 = 99 − 95 = 4. Multiply by 5: 4 × 5 = 20 ≡ 20 − 19 = 1.

5¹¹⁷ mod 19 = 1
5
Step 5 — Verify via Fermat's Little Theorem

Since 19 is prime and gcd(5, 19) = 1, Fermat's Little Theorem tells us 5¹⁸ ≡ 1 (mod 19). Now 117 = 6 × 18 + 9, so 5¹¹⁷ ≡ 5⁹ (mod 19). We can verify: 5⁹ = 5⁸ × 5 ≡ 4 × 5 = 20 ≡ 1 (mod 19). The answer checks out perfectly.

Confirmed: 5¹¹⁷ mod 19 = 1 ✓

SECTION 7

Method Comparisons & Practical Considerations

While the binary method (repeated squaring) is the most commonly taught algorithm for fast modular exponentiation, several variant techniques exist, each with different trade-offs between memory usage, number of multiplications, and resistance to side-channel attacks. Understanding these trade-offs is critical for applications in cryptographic engineering.

Method	Multiplications (k-bit exponent)	Memory	Side-Channel Safety
Naive	O(2ᵏ) — exponential in bit-length	O(1)	Constant time (trivially)
Binary (R→L)	≤ 2k: k squarings + up to k multiplies	O(1) extra	Variable — leaks Hamming weight of e
Binary (L→R)	≤ 2k: same asymptotic cost	O(1) extra	Variable — same leakage concern
m-ary / Sliding Window	~k/(log₂ w) + $2^w$ precomputations	O(2ʷ) precomputed values	Improved but not constant-time
Montgomery Ladder	2k: exactly k squarings + k multiplies	O(1) extra	Constant-time — resistant to timing attacks

Comparison of modular exponentiation methods for a k-bit exponent

🔒

SECURITY MATTERS

In pure mathematics, any method that produces the correct answer suffices. But in cryptography, the execution pattern matters as much as the final result. If an attacker can distinguish between "square only" and "square then multiply" iterations — via power analysis, cache timing, or electromagnetic emanation — they can reconstruct the private exponent bit by bit. The Montgomery ladder eliminates this vulnerability by performing the same operations regardless of the bit value, analogous to a factory assembly line that performs every station's task on every unit, even if some tasks produce 'dummy' output — ensuring identical power and timing signatures.

SECTION 8

Connection to Cryptography & Advanced Theory

Modular exponentiation is not merely a computational convenience; it is the fundamental operation underlying the security of the digital world. The asymmetry between the ease of computing b^e mod m (polynomial time via repeated squaring) and the apparent difficulty of inverting this operation — recovering e from b, m, and b^e mod m, known as the discrete logarithm problem — is the trapdoor upon which Diffie-Hellman, ElGamal, and DSA are built. Similarly, RSA relies on the difficulty of factoring the modulus to prevent an adversary from computing the private decryption exponent.

Protocol / Application	Role of Modular Exponentiation	Hard Problem Assumed
RSA Encryption/Decryption	Ciphertext c = mᵉ mod n; plaintext m = cᵈ mod n	Integer factorization of n = pq
Diffie-Hellman Key Exchange	Each party computes gᵃ mod p and gᵇ mod p; shared secret is gᵃᵇ mod p	Decisional/Computational DLP
ElGamal Encryption	Encryption involves gᵏ mod p and m · yᵏ mod p for random k	Discrete Logarithm Problem
Miller-Rabin Primality Test	Tests $a^d$ mod n for witnesses to compositeness; core loop uses repeated squaring	Probabilistic primality certification
Elliptic Curve Cryptography	Scalar multiplication kP on a curve is the additive analog of modular exponentiation, using double-and-add	Elliptic Curve DLP (ECDLP)

Cryptographic protocols and their dependence on modular exponentiation

Looking ahead, the advent of quantum computing threatens the discrete logarithm and factoring assumptions through Shor's algorithm, which solves both problems in polynomial time on a quantum computer. This has spurred the development of post-quantum cryptography based on lattice problems, coding theory, and hash-based signatures — problems that do not reduce to modular exponentiation. Nevertheless, understanding fast powering remains essential: it appears in isogeny-based schemes, is used in the proof-of-work mechanisms of some blockchain protocols, and continues to be the workhorse of current-generation TLS.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why we can reduce modulo m after every multiplication during modular exponentiation without affecting the final result. Which algebraic property of modular arithmetic justifies this?

Show answer

The key property is that modular arithmetic is compatible with multiplication: (a × b) mod m = ((a mod m) × (b mod m)) mod m. This means that the remainder of a product depends only on the remainders of its factors. Consequently, reducing intermediate results modulo m at any point does not alter the final residue. This property — formally stated as ℤ/mℤ forming a ring under addition and multiplication — ensures that modular exponentiation is well-defined and that we can keep all intermediate values bounded by m, preventing exponential growth in the size of numbers being manipulated.

Question 2: BASIC CALCULATION

Compute 2¹⁰ mod 13 using the binary method of repeated squaring. Show your squaring table and identify which entries contribute to the final product.

Show answer

First, 10 = 1010₂ = 2³ + 2¹. Building the squaring table: 2¹ ≡ 2, 2² ≡ 4, 2⁴ ≡ 4² = 16 ≡ 3, 2⁸ ≡ 3² = 9. The 1-bits are at positions 1 and 3, so we select 2² ≡ 4 and 2⁸ ≡ 9. Multiplying: 4 × 9 = 36 ≡ 36 − 2 × 13 = 10 (mod 13). Therefore, 2¹⁰ mod 13 = 10. This required only 3 squarings and 1 multiplication, compared to 9 sequential multiplications naively.

Question 3: INTERMEDIATE

Compute 11²³ mod 29 using the left-to-right (Horner-style) binary method. The binary representation of 23 is 10111₂. Show each iteration, indicating when you square and when you multiply by the base.

Show answer

In the left-to-right method, we scan the bits of 23 = 10111₂ from the most significant to least significant. Initialize result = 1. Bit 4 = 1: result = 1² × 11 = 11. Bit 3 = 0: result = 11² = 121 ≡ 121 − 4 × 29 = 121 − 116 = 5 (mod 29). Bit 2 = 1: result = 5² × 11 = 25 × 11 = 275 ≡ 275 − 9 × 29 = 275 − 261 = 14 (mod 29). Bit 1 = 1: result = 14² × 11 = 196 × 11. Now 196 mod 29 = 196 − 6 × 29 = 196 − 174 = 22, so 22 × 11 = 242 ≡ 242 − 8 × 29 = 242 − 232 = 10 (mod 29). Bit 0 = 1: result = 10² × 11 = 100 × 11. Now 100 mod 29 = 100 − 3 × 29 = 100 − 87 = 13, so 13 × 11 = 143 ≡ 143 − 4 × 29 = 143 − 116 = 27 (mod 29). Therefore 11²³ mod 29 = 27.

Question 4: APPLIED

In a simplified RSA system, Alice chooses primes p = 11 and q = 13, giving n = 143 and φ(n) = 120. She selects public exponent e = 7 and computes private exponent d such that ed ≡ 1 (mod 120). Find d, then encrypt the message M = 9 by computing C = 9⁷ mod 143 using repeated squaring, and verify by decrypting

C^d

mod 143.

Show answer

First, find d: we need 7d ≡ 1 (mod 120). Using the extended Euclidean algorithm: 120 = 17 × 7 + 1, so 1 = 120 − 17 × 7, meaning d = −17 ≡ 103 (mod 120). Encryption: 7 = 111₂. Squaring table: 9¹ ≡ 9, 9² = 81, 9⁴ ≡ 81² = 6561 ≡ 6561 mod 143 = 6561 − 45 × 143 = 6561 − 6435 = 126. Since 7 = 4 + 2 + 1, we compute 9⁷ = 9⁴ × 9² × 9¹ ≡ 126 × 81 × 9 mod 143. Now 126 × 81 = 10206, and 10206 mod 143 = 10206 − 71 × 143 = 10206 − 10153 = 53. Then 53 × 9 = 477, and 477 mod 143 = 477 − 3 × 143 = 477 − 429 = 48. So C = 48. Decryption: 48¹⁰³ mod 143. Using Fermat/CRT shortcuts or repeated squaring with 103 = 1100111₂, one can verify that 48¹⁰³ mod 143 = 9, recovering the original message.

Question 5: CRITICAL THINKING

Prove that the binary method of exponentiation computes b^e mod m correctly for all non-negative integers e. Specifically, formulate and prove a loop invariant for the right-to-left algorithm. (Hint: at the start of iteration i, let eᵢ denote the remaining exponent after i right-shifts, and let baseᵢ = b^(

2^i

) mod m.)

Show answer

Define the loop invariant: at the start of the i-th iteration, result × base^(eᵢ) ≡

b^e

(mod m), where eᵢ = ⌊e/2ⁱ⌋ and baseᵢ ≡ b^(

2^i

) (mod m). Base case (i = 0): result = 1, base₀ = b, e₀ = e, so 1 ×

b^e

≡

b^e

(mod m). Inductive step: suppose the invariant holds at iteration i. If the low bit of eᵢ is 1, result is updated to result × baseᵢ, reducing the remaining exponent by 1 (making it even). Then base is squared to baseᵢ₊₁ = baseᵢ² ≡

b^{2^{i+1}}

(mod m), and eᵢ is right-shifted to eᵢ₊₁ = ⌊eᵢ/2⌋. The product result × baseᵢ₊₁^(eᵢ₊₁) accounts for all bits processed so far plus the remaining power, preserving the invariant. Termination: the loop ends when eᵢ = 0, at which point the invariant gives result × base⁰ = result ≡

b^e

(mod m). Since eᵢ decreases by at least a factor of 2 each iteration, the loop terminates in ⌊log₂ e⌋ + 1 steps, establishing both correctness and the O(log e) complexity.

SUMMARY

Lesson Summary

Summary

Modular exponentiation — computing b^e mod m — is made computationally feasible by the binary method of repeated squaring, which exploits the binary representation of the exponent to reduce the number of multiplications from O(e) to O(log e). The algorithm works by building a table of successive squares of the base modulo m, then multiplying together only those entries whose corresponding binary digit in e is 1. The multiplicative closure of ℤ/mℤ guarantees that reducing after every operation preserves correctness while keeping intermediate values bounded.

This technique is the computational foundation of RSA encryption, Diffie-Hellman key exchange, ElGamal encryption, and primality testing. Variants such as the Montgomery ladder provide constant-time execution to resist side-channel attacks, while sliding window methods trade memory for fewer multiplications. The security of all these systems rests on the asymmetry between the efficiency of modular exponentiation (easy) and the presumed hardness of the discrete logarithm problem (hard) — an asymmetry that remains one of the most consequential unsolved questions in computational complexity theory.

Execution Trace: 73277^{327}7327 mod 853

Execution Trace: $7^{327}$ mod 853