Difficulty: Intermediate | Prerequisites: Modular arithmetic basics (EECS 376 Section 10), binary number representation.
Modular exponentiation is the computational backbone of RSA and Diffie-Hellman cryptography. When you encrypt or decrypt a message using RSA, you are computing something like m^e mod n, where the exponent can be hundreds of digits long. Doing this naively (multiply, multiply, multiply) would take an astronomical number of steps. Fast modular exponentiation, built on repeated squaring, brings the cost down to O(log b) multiplications, making public-key cryptography practical. You should already be comfortable with basic modular arithmetic identities before reading on.
You can compute a^b mod n efficiently by breaking the exponent into its binary representation and squaring repeatedly, rather than multiplying b times. This takes O(log b) multiplications instead of O(b), which is the reason RSA works at real-world key sizes.
Modular arithmetic
Arithmetic where numbers "wrap around" after reaching a modulus n. Formally, a mod n is the remainder when a is divided by n. In simple terms, think of a clock: 15 mod 12 = 3, because after going round the dial you land on 3.
Modular exponentiation
Computing a^b mod n for large values of b. This is the core operation in RSA encryption and decryption. Think of it as raising a number to a huge power, but keeping the result small by taking the remainder at each step.
Repeated squaring (square-and-multiply)
An algorithm that computes a^b mod n in O(log b) multiplications by repeatedly squaring the base and reducing mod n, rather than multiplying b times. In simple terms, instead of multiplying 7 by itself 256 times, you square it 8 times.
Binary representation of the exponent
Writing the exponent b as a sum of powers of 2 (its binary digits). This lets you decompose a^b into a product of terms whose exponents are each a power of 2. Think of it as breaking a big job into smaller pieces you have already computed along the way.
Two identities make fast exponentiation possible:
Multiplication rule: (a · b) mod n = ((a mod n) · (b mod n)) mod n. You can reduce each factor mod n before multiplying, keeping intermediate values small.
Exponentiation rule: (a^b) mod n = ((a mod n)^b) mod n. You can reduce the base first, then raise it to the power.
In RSA, these identities are why encryption (m^e mod n) and decryption (c^d mod n) work without ever computing the astronomically large unmodded value.
When b is a power of 2, you can write a^b = (a^(b/2))^2. Keep halving the exponent and squaring the result:
a^b = (((a^2)^2)^...)^2, with log₂(b) squarings total.
At each step, reduce mod n so the numbers stay bounded.
This gives O(log b) multiplications rather than O(b).
For arbitrary b, write b in binary: b = b₀·2⁰ + b₁·2¹ + ... + bᵣ·2ʳ.
Then a^b = a^(b₀·2⁰) · a^(b₁·2¹) · ... · a^(bᵣ·2ʳ).
Each factor a^(2^i) is already computed during the repeated-squaring pass. You only multiply in the factors where the corresponding binary digit bᵢ = 1.
The repeated-squaring pass costs O(log b) multiplications.
Collecting the product costs at most another O(log b) multiplications (one per binary digit).
Total: O(log b).
(a \cdot b) \bmod n = ((a \bmod n)(b \bmod n)) \bmod na^b \bmod n = (a \bmod n)^b \bmod na^b = a^{b_0 \cdot 2^0} \cdot a^{b_1 \cdot 2^1} \cdots a^{b_r \cdot 2^r}Compute 7^256 mod 13.
7^1 mod 13 = 7
7^2 = 49 mod 13 = 10
7^4 = 10 × 10 = 100 mod 13 = 9
7^8 = 9 × 9 = 81 mod 13 = 3
7^16 = 3 × 3 = 9 mod 13 = 9
7^32 = 9 × 9 = 81 mod 13 = 3
7^64 = 3 × 3 = 9 mod 13 = 9
7^128 = 9 × 9 = 81 mod 13 = 3
7^256 = 3 × 3 = 9 mod 13 = 9
Only 8 multiplications (log₂ 256 = 8).
Compute 7^117 mod 13.
First, write 117 in binary: 117 = 1110101₂ = 64 + 32 + 16 + 4 + 1.
Reuse the squaring table from Example 1:
7^1 mod 13 = 7
7^4 mod 13 = 9
7^16 mod 13 = 9
7^32 mod 13 = 3
7^64 mod 13 = 9
Multiply the terms whose binary digits are 1:
7^117 mod 13 = (7 × 9 × 9 × 3 × 9) mod 13 = 63 × 27 × 9 mod 13 = (63 mod 13) × (27 mod 13) × 9 mod 13 = 11 × 1 × 9 mod 13 = 99 mod 13 = 8.
Students often think you must compute a^b first and then take mod n at the end. You do not. Reducing mod n at every intermediate step is both correct (by the multiplication rule) and essential for keeping numbers small.
Some students confuse the number of multiplications with the size of the exponent. Repeated squaring uses O(log b) multiplications, not O(b). The exponent 256 needs only 8 squarings.
When decomposing b into binary, students sometimes forget to include only the powers of 2 where the binary digit is 1. If a bit is 0, that factor is a^0 = 1 and contributes nothing to the product.
A common error in worked problems is forgetting to reduce mod n after each multiplication. Skipping this step leads to numbers that grow quickly and defeats the purpose of the algorithm.
⚠️ Expect to be asked to compute a^b mod n by hand using repeated squaring. Know both cases: power-of-2 exponent and arbitrary exponent via binary decomposition.
⚠️ You may be asked to state the time complexity. The answer is O(log b) multiplications. Be prepared to justify why by referencing the binary representation.
⚠️ RSA questions often ask you to show that c^d mod n = m using these identities. Walk through the chain: c^d = (m^e)^d = m^(ed) = m mod n.
⚠️ This material connects directly to the security argument for RSA: if modular exponentiation were not efficient, RSA would be impractical; if its inverse (discrete log) were efficient, RSA would be insecure.
True or false: To compute a^b mod n, you must first compute a^b and then reduce mod n. False. You reduce at every step.
How many multiplications does repeated squaring need to compute a^(1024) mod n? 10 (since log₂ 1024 = 10).
Fill in the blank: To handle an arbitrary exponent b, you decompose b into its ______ representation. Binary.
True or false: (a · b) mod n = (a mod n) · (b mod n). False as written. The right-hand side still needs a final mod n: ((a mod n) · (b mod n)) mod n.
What is 7^4 mod 13? 9 (since 7^2 = 49 ≡ 10, and 10 × 10 = 100 ≡ 9 mod 13).
Q: Compute 3^20 mod 7 using repeated squaring.
A: 3^1 = 3. 3^2 = 9 mod 7 = 2. 3^4 = 4 mod 7 = 4. 3^8 = 16 mod 7 = 2. 3^16 = 4 mod 7 = 4. Since 20 = 16 + 4, we get 3^20 = 3^16 × 3^4 = 4 × 4 = 16 mod 7 = 2.
Q: Why is it correct to reduce mod n at each step of the computation, rather than only at the end?
A: Because of the modular multiplication identity: (a × b) mod n = ((a mod n) × (b mod n)) mod n. Reducing early does not change the final result, and it keeps intermediate values bounded by n.
Q: How many multiplications are needed to compute a^b mod n when b has a k-bit binary representation?
A: O(k). The squaring pass takes k - 1 squarings, and collecting the product takes at most k - 1 additional multiplications. Since k = floor(log₂ b) + 1, this is O(log b).
Q: In RSA, show why c^d mod n recovers the original message m, given c = m^e mod n and ed ≡ 1 mod φ(n).
A: c^d mod n = (m^e mod n)^d mod n = m^(ed) mod n. Because ed ≡ 1 mod φ(n), Euler's theorem gives m^(ed) ≡ m mod n. So decryption recovers m.
This connects to RSA encryption and decryption because both operations are modular exponentiations with large exponents. Without fast modular exponentiation, RSA key sizes used in practice (2048+ bits) would be computationally infeasible.
It also connects to the Discrete Logarithm problem and the Baby-step Giant-step algorithm. Fast exponentiation is the "easy direction" (computing g^x mod p is efficient), while the inverse (finding x given g^x mod p) is believed to be hard, and that asymmetry is what makes Diffie-Hellman secure.
The binary decomposition idea reappears in other "fast" algorithms in this course, such as fast matrix exponentiation for recurrence relations.
Modular exponentiation, repeated squaring, square-and-multiply, fast exponentiation, binary method, modular arithmetic, RSA encryption, RSA decryption, modular inverse, Euler's theorem, Fermat's little theorem, EECS 376, discrete logarithm, Diffie-Hellman, public-key cryptography, O(log b) exponentiation, power mod n.