1
Squaring halves the exponent
a^{2k} = (a^k)², so each squaring doubles the exponent reached. Reading b in binary tells you which squarings to multiply in.
Lesson · Number Theory and Cryptography · Congruences
Modular Exponentiation
Repeated squaring computes aᵇ mod m in about 2 log₂ b multiplications rather than b of them, reducing at every step so the numbers stay small. It is what makes RSA possible.
square and multiply: read the exponent in binary
reduce mod m at EVERY step
cost: about 2·log₂(b) multiplications, not b
7^128 mod 13 in 7 squarings, not 128 multiplications
Logarithmic, not linear
Core ideas
What this lesson establishes
Two ideas, each essential: halve the exponent by squaring, and reduce the numbers by the modulus.
2
Reducing keeps the numbers small
Without reducing, a^b for a 1024-bit b has more digits than there are atoms in the universe. With reducing, every intermediate is below m².
3
Both are necessary
Fast exponentiation without reduction produces unrepresentable numbers; reduction without fast exponentiation takes b multiplications.
The material
Square and multiply
The algorithm, the cost, and why RSA depends on it.
MODPOW(a, b, m):
result = 1
base = a mod m
while b > 0:
if b is odd: result = (result · base) mod m
base = (base · base) mod m
b = b div 2
return result
The loop reads b in binary from the least significant bit. base holds a^{2^i} mod m at step i, and the result accumulates exactly those powers whose bit is set. Since b = Σ bᵢ2ⁱ, the product of the selected powers is a^b.
Theorem · Correctness
MODPOW returns a^b mod m.
The loop invariant is result · base^b ≡ a^{b₀} (mod m), where b₀ is the original exponent.
Initially result = 1 and base = a, so it holds. If b is even, base^b = (base²)^{b/2}, and the update preserves it. If b is odd, base^b = base · (base²)^{(b−1)/2}, and multiplying result by base before the halving preserves it.
At exit b = 0, so the invariant reads result ≡ a^{b₀}.
□
The cost
The loop runs ⌊log₂ b⌋ + 1 times, with one squaring per iteration and at most one extra multiplication. The last squaring is never used, so the useful count is ⌊log₂ b⌋ squarings plus one multiplication per set bit — at most about 2 log₂ b modular multiplications in all.
b = 128: naive 128 multiplications, fast 8 squarings
b = 10⁶: naive a million, fast about 20 squarings
b = 2¹⁰²⁴: naive impossible, fast about 1024 squarings
Example · 7^128 mod 13
7² = 49 ≡ 10; 10² = 100 ≡ 9; 9² = 81 ≡ 3; 3² = 9; 9² = 81 ≡ 3; 3² ≡ 9; 9² ≡ 3. Since 128 = 2⁷, seven squarings give 7^128 ≡ 3 (mod 13). No number above 144 ever appeared.
That bound is the second essential point: every intermediate is a product of two numbers below m, hence below m². For a 2048-bit modulus the intermediates are 4096 bits, which is entirely routine, while a^b itself would have about 2^1024 bits.
Where it is used
- RSA (“RSA Encryption”): both encryption and decryption are a single modular exponentiation, with 2048-bit exponents.
- Diffie–Hellman key exchange and the whole family of discrete-logarithm systems.
- Primality testing: Fermat and Miller–Rabin both compute a^{n−1} mod n, which is only feasible this way.
It is worth appreciating the asymmetry the algorithm creates. Computing a^b mod m is fast; recovering b from a, a^b mod m and m — the discrete logarithm — is believed hard. A great deal of cryptography lives in that gap.
Interactive
Number theory workbench
Algorithms with their traces
Method
Computing a modular power
Binary exponent, reduce every step.
1
Write the exponent in binary
100 = 1100100₂. The set bits are the powers you will multiply in.
2
Square repeatedly, reducing each time
a, a², a⁴, a⁸, … each reduced mod m. Never let a value exceed m².
3
Multiply in the powers matching set bits
Reducing after every multiplication. The order does not matter.
4
Check the size of every intermediate
If a number larger than m² appears, a reduction was skipped and the advantage is lost.
Modular exponentiation
Score 0 / 0Choose the answer you can justify.
3^200 mod 50
200 = 11001000₂, so the set bits are at positions 3, 6 and 7.
bit power of 3 value mod 50 used?
0 3^1 3 no
1 3^2 9 no
2 3^4 31 no (9² = 81 ≡ 31)
3 3^8 11 YES (31² = 961 ≡ 11)
4 3^16 21 no (11² = 121 ≡ 21)
5 3^32 41 no (21² = 441 ≡ 41)
6 3^64 31 YES (41² = 1681 ≡ 31)
7 3^128 11 YES (31² ≡ 11)
result = 11 · 31 · 11 mod 50
= 341 mod 50 · 11 = 41 · 11 = 451 ≡ 1 (mod 50)
7 squarings and 3 multiplications, against 199 the naive way.
The powers began repeating — 3^4 ≡ 3^64 ≡ 31 — because the multiplicative order of 3 modulo 50 divides φ(50) = 20. “Fermat's Little Theorem and Euler's Theorem” explains that, and it is why the answer came out as 1.
Common mistakes
1
Reducing the exponent modulo mExponents reduce modulo φ(m), not m, and only when the base is coprime to m. “Fermat's Little Theorem and Euler's Theorem” states the rule.
2
Computing a^b before reducingThe intermediate is astronomically large. Reducing at every step is the whole point.
3
Multiplying in the wrong powersOnly the set bits of the exponent contribute. Writing b in binary first makes this mechanical.
Check your understanding
✓
Finish when you can trace the algorithm on paper.
Compute 5^117 mod 19 by square and multiply, writing 117 in binary first: 1110101₂, five set bits. Six squarings to reach 5^64, five factors to multiply together, and no intermediate above 361.
Note: The same algorithm works for any associative operation: matrix powers, compositions of functions, and group elements generally. The exponent's binary expansion is what is being exploited, and multiplication is incidental.