Difficulty: Intermediate
Prerequisites: Divisibility and the Division Algorithm notes (the companion document). You need to be comfortable with the definition of a | b and with computing quotients and remainders before starting here.
Modular arithmetic turns the idea of remainders into a full algebraic system where you can add, subtract, and multiply. This is the mathematical engine behind public-key cryptography (RSA, Diffie-Hellman) and many hashing schemes. Fast modular exponentiation is the algorithm that makes it practical to compute things like b^n mod m when n is hundreds of digits long, which is exactly what happens every time your browser opens an HTTPS connection.
Two integers are congruent modulo M if they have the same remainder when divided by M. You can add and multiply congruences freely, which lets you reduce enormous calculations to small-number arithmetic. Fast modular exponentiation uses the binary representation of the exponent to compute b^n mod m in only about log₂(n) squarings instead of n multiplications.
Congruent modulo M (a ≡ b (mod M))
a and b are integers, M is a positive integer. a is congruent to b modulo M if and only if M | (a − b).
In simple terms, a and b leave the same remainder when you divide each by M.
Not congruent modulo M (a ≢ b (mod M))
M does not divide (a − b). The two integers have different remainders when divided by M.
Modular addition (Theorem 3, part 1)
If a ≡ b (mod M) and c ≡ d (mod M), then a + c ≡ b + d (mod M).
Think of it as: you can add the remainders and the result still has the right remainder.
Modular multiplication (Theorem 3, part 2)
If a ≡ b (mod M) and c ≡ d (mod M), then ac ≡ bd (mod M).
Think of it as: you can multiply the remainders and the result still has the right remainder.
Modular arithmetic corollary
(a + b) mod M = ((a mod M) + (b mod M)) mod M, and (ab) mod M = ((a mod M) × (b mod M)) mod M.
In simple terms, you can reduce each number to its remainder first, do the arithmetic, then take the remainder again. The answer is the same as working with the full numbers.
Fast modular exponentiation (repeated squaring)
An algorithm to compute b^n mod m efficiently by expressing n in binary and building up the answer through successive squarings, reducing mod m at each step.
Think of it as: instead of multiplying b by itself n times, you square repeatedly and only multiply in the squares that correspond to 1-bits in n's binary form.
Let a and b be integers and M a positive integer. a is congruent to b modulo M (written a ≡ b (mod M)) if and only if M | (a − b).
Example: 17 ≡ 5 (mod 6) because 6 | (17 − 5) = 12. Both 17 and 5 have remainder 5 when divided by 6.
Example: 24 ≢ 14 (mod 6) because 6 ∤ (24 − 14) = 10.
Let M be a positive integer. If a ≡ b (mod M) and c ≡ d (mod M), then:
a + c ≡ b + d (mod M)
ac ≡ bd (mod M)
Proof of part 1 (addition):
Since a ≡ b (mod M), we have M | (a − b). Since c ≡ d (mod M), we have M | (c − d). By Theorem 1a (divisibility distributes over addition), M | ((a − b) + (c − d)), which simplifies to M | ((a + c) − (b + d)). Therefore a + c ≡ b + d (mod M).
Proof of part 2 (multiplication):
Since a ≡ b (mod M), we can write a − b = kM for some integer k, so a = b + kM. Since c ≡ d (mod M), we can write c − d = nM for some integer n, so c = d + nM. Then ac = (b + kM)(d + nM) = bd + (dk + bn)M + (kn)M². So ac − bd = M(dk + bn + knM), meaning M | (ac − bd), and therefore ac ≡ bd (mod M).
For any positive integer M and integers a, b:
(a + b) mod M = ((a mod M) + (b mod M)) mod M
(ab) mod M = ((a mod M) × (b mod M)) mod M
This is enormously useful: you can reduce each operand modulo M before doing the arithmetic, keeping numbers small throughout.
Example 3: Using Theorem 3
We know 7 ≡ 2 (mod 5) and 11 ≡ 1 (mod 5). So:
18 = 7 + 11 ≡ 2 + 1 ≡ 3 (mod 5)
77 = 7 × 11 ≡ 2 × 1 ≡ 2 (mod 5)
Example 4: (123 × 234) mod 5
123 mod 5 = 3, and 234 mod 5 = 4. By the corollary: (123 × 234) mod 5 = (3 × 4) mod 5 = 12 mod 5 = 2.
Example 5: (19³ mod 31)⁴ mod 23
First compute 19³ mod 31:
19 × 19 = 361; 361 mod 31 = 20 (since 361 = 11 × 31 + 20)
20 × 19 = 380; 380 mod 31 = 8 (since 380 = 12 × 31 + 8)
So 19³ mod 31 = 8. Now compute 8⁴ mod 23:
8² = 64; 64 mod 23 = 18, but it is more convenient to note 64 ≡ −5 (mod 23)
(−5) × (−5) = 25; 25 mod 23 = 2
So (19³ mod 31)⁴ mod 23 = 2.
Computing b^n mod m directly means multiplying b by itself n times. When n is very large (hundreds of digits in cryptography), this is completely impractical. The numbers overflow, and it takes far too long.
Express the exponent n in binary. Then b^n breaks into a product of powers of b where each power is a power of 2. You build these by squaring repeatedly, reducing mod m at each step to keep numbers small.
procedure modular_exp(b, n = (a_{k-1} a_{k-2} ... a_1 a_0)_2, m):
x := 1
power := b mod m
for i := 0 to k-1:
if a_i = 1 then x := (x × power) mod m
power := (power × power) mod m
return x
The variable "power" tracks b^(2^i) mod m at each step. Whenever the i-th bit of n is 1, you multiply x by the current power.
Step 1: Convert the exponent to binary. 29 = 16 + 8 + 4 + 1 = (11101)₂.
So 572²⁹ = 572¹⁶ × 572⁸ × 572⁴ × 572¹.
Step 2: Build the powers of 572 by repeated squaring mod 713.
572¹ mod 713 = 572
572² mod 713 = 630
572⁴ mod 713 = 630² mod 713 = 472
572⁸ mod 713 = 472² mod 713 = 328
572¹⁶ mod 713 = 328² mod 713 = 634
Step 3: Multiply the powers corresponding to the 1-bits.
572²⁹ mod 713 = (572 × 472 × 328 × 634) mod 713.
Computing in stages: (572 × 472) mod 713 = 470, then (328 × 634) mod 713 = 469, then (470 × 469) mod 713 = 113.
Result: 572²⁹ mod 713 = 113.
Step 1: 644 = (1,010,000,100)₂ = 512 + 128 + 4.
So 3⁶⁴⁴ = 3⁵¹² × 3¹²⁸ × 3⁴.
Step 2: Build powers by repeated squaring mod 645.
3¹ mod 645 = 3
3² mod 645 = 9
3⁴ mod 645 = 81
3⁸ mod 645 = 111
3¹⁶ mod 645 = 66
3³² mod 645 = 486
3⁶⁴ mod 645 = 126
3¹²⁸ mod 645 = 396
3²⁵⁶ mod 645 = 81
3⁵¹² mod 645 = 111
Step 3: Multiply the three relevant powers.
x starts at 1. Bit 2 is 1, so x = (1 × 81) mod 645 = 81. Bit 7 is 1, so x = (81 × 396) mod 645 = 471. Bit 9 is 1, so x = (471 × 111) mod 645 = 36.
Result: 3⁶⁴⁴ mod 645 = 36.
Congruence definition
a ≡ b (mod M) ⟺ M | (a − b)
Modular addition
If a ≡ b (mod M) and c ≡ d (mod M), then a + c ≡ b + d (mod M)
Modular multiplication
If a ≡ b (mod M) and c ≡ d (mod M), then ac ≡ bd (mod M)
Corollary (reduce-then-compute)
(a + b) mod M = ((a mod M) + (b mod M)) mod M
(ab) mod M = ((a mod M) × (b mod M)) mod M
Fast modular exponentiation complexity
For an exponent n, the algorithm uses at most 2 × log₂(n) modular multiplications.
RSA encryption relies entirely on modular exponentiation with very large primes. When your browser negotiates an HTTPS connection, it computes something equivalent to b^n mod m where n can be 2048 bits long. Without the fast modular exponentiation algorithm, this would be computationally infeasible. Hash functions, digital signatures, and Diffie-Hellman key exchange all depend on the same modular arithmetic properties covered here.
Students often think a ≡ b (mod M) means "a mod M equals b." It does not. It means a and b have the same remainder mod M, or equivalently, M divides their difference. 17 ≡ 5 (mod 6) is true, but 17 mod 6 = 5, not "17 mod 6 = 5 (mod 6)."
Modular arithmetic does not support division the same way it supports addition and multiplication. You cannot freely divide both sides of a congruence. (This is covered properly in later sections on modular inverses.)
When doing fast modular exponentiation, students sometimes forget to reduce mod m after each squaring step. The whole point of the algorithm is to keep intermediate values small; skipping the reduction defeats the purpose and can cause overflow.
Students sometimes confuse the bit ordering in the exponent. The algorithm processes bits from least significant (rightmost, a₀) to most significant. Make sure you read the binary representation in the correct direction.
⚠️ The proof of Theorem 3 (both parts) is a common exam question. Be ready to write it from scratch using the definition of congruence and Theorem 1.
⚠️ The corollary (reduce-then-compute) is tested as a computation problem: you will be given large products or sums and asked to find the result mod M without computing the full product.
⚠️ Fast modular exponentiation is tested both as a trace-through ("show the table of successive squarings and the accumulator") and as a programming exercise. Know the pseudocode and be able to trace it by hand for a given base, exponent, and modulus.
⚠️ Using negative equivalents (e.g. replacing 64 mod 23 with −5 because 64 = 3 × 23 − 5) is a common exam trick to simplify multiplication. Practise spotting when a negative representative makes the arithmetic easier.
True or false: 25 ≡ 4 (mod 7).
Fill in the blank: (47 × 63) mod 10 = ___.
True or false: If a ≡ b (mod M), then a − b is a multiple of M.
How many modular multiplications does fast modular exponentiation need to compute b^1024 mod m?
Fill in the blank: 3² mod 645 = ___.
Answers: 1. True (25 − 4 = 21, and 7 | 21). 2. 1 (47 mod 10 = 7, 63 mod 10 = 3, 7 × 3 = 21, 21 mod 10 = 1). 3. True (that is the definition). 4. At most 20 (2 × log₂(1024) = 2 × 10). 5. 9.
Q: Prove that if a ≡ b (mod M) and c ≡ d (mod M), then a + c ≡ b + d (mod M).
A: By definition, M | (a − b) and M | (c − d). By the additive property of divisibility (Theorem 1a), M | ((a − b) + (c − d)) = M | ((a + c) − (b + d)). By the definition of congruence, a + c ≡ b + d (mod M).
Q: Compute 7⁵ mod 11 using the corollary (reduce at each step).
A: 7² = 49; 49 mod 11 = 5. 7⁴ = (7²)² ≡ 5² = 25; 25 mod 11 = 3. 7⁵ = 7⁴ × 7 ≡ 3 × 7 = 21; 21 mod 11 = 10. So 7⁵ mod 11 = 10.
Q: Use fast modular exponentiation to compute 2¹³ mod 17. Show the table of successive squarings.
A: 13 = (1101)₂ = 8 + 4 + 1. Squarings: 2¹ mod 17 = 2; 2² mod 17 = 4; 2⁴ mod 17 = 16; 2⁸ mod 17 = 256 mod 17 = 1. Accumulate: x = 1. Bit 0 = 1, x = (1 × 2) mod 17 = 2. Bit 2 = 1, x = (2 × 16) mod 17 = 32 mod 17 = 15. Bit 3 = 1, x = (15 × 1) mod 17 = 15. So 2¹³ mod 17 = 15.
Q: Explain why fast modular exponentiation is necessary for RSA.
A: RSA uses exponents that are typically 2048 bits long. Computing b^n by multiplying b by itself n times would require roughly 2^2048 multiplications, which is computationally infeasible. Fast modular exponentiation reduces this to about 2 × 2048 = 4096 modular multiplications by exploiting the binary representation of the exponent and reducing mod m at each step.
Modular arithmetic is the foundation for the GCD and Extended Euclidean Algorithm (KR 4.3), which in turn enables computing modular inverses. Those inverses are essential for RSA decryption. The fast modular exponentiation algorithm here is also the basis for primality testing algorithms like Miller-Rabin, which the course may cover later. The concept of congruence classes leads to the algebraic structure of groups and rings in abstract algebra.
modular arithmetic, congruence, congruent modulo, mod operator, modular addition, modular multiplication, Theorem 3 congruences, corollary mod, fast modular exponentiation, repeated squaring, binary exponentiation, square and multiply, RSA, public-key cryptography, Diffie-Hellman, KR 4.1, KR 4.2.4, Purdue CS Foundations, number theory, discrete mathematics, modular inverse, remainder arithmetic