🔢 Unit VII: Number Theoretic Algorithms
Design and Analysis of Algorithms (MIT121)
Second Semester — Master of Information Technology
§ 7.1 & 7.2 — Introduction & Notations
1. Introduction to Number Theoretic Algorithms
Number theory is the branch of pure mathematics dealing with properties of integers. In computer science, number theoretic algorithms are the backbone of cryptography, hashing, random number generation, and many combinatorial algorithms.
Why Number Theory in Algorithms? Many modern cryptographic systems (RSA, Diffie-Hellman) rely entirely on number theoretic hardness. Even efficient data structures like hash maps use modular arithmetic under the hood.
Key Application Areas
- Public-Key Cryptography: RSA encryption uses GCD, modular exponentiation, and primality testing.
- Digital Signatures: Algorithms like DSA depend on modular arithmetic.
- Hashing: Hash functions use modular reduction for uniform distribution.
- Random Number Generation: Linear congruential generators use modular operations.
- Error Detection Codes: CRC and checksum algorithms use polynomial arithmetic modulo 2.
The algorithms discussed in this unit run in time polynomial in the number of bits of the input, not polynomial in the value of the input itself — a crucial distinction.
If the input number is n, then its binary representation has ⌊lg n⌋ + 1 bits. Algorithms like Euclid's run in O(lg n) bit operations, which means polynomial in the input size.
2. Number Theoretic Notations
Divisibility
We say "d divides n" (written d | n) if there exists an integer k such that n = dk. Equivalently, n is a multiple of d, and d is a divisor (factor) of n.
d | n if and only if ∃k ∈ ℤ such that n = dk. We write d ∤ n if d does not divide n.
| Notation | Meaning | Example |
|---|---|---|
d | n | d divides n | 3 | 12 (since 12 = 3×4) |
d ∤ n | d does not divide n | 5 ∤ 13 |
gcd(a, b) | Greatest Common Divisor | gcd(12, 8) = 4 |
lcm(a, b) | Least Common Multiple | lcm(4, 6) = 12 |
a ≡ b (mod n) | a is congruent to b modulo n | 17 ≡ 5 (mod 12) |
a mod n | Remainder of a ÷ n | 17 mod 12 = 5 |
Prime Numbers & Coprimality
A positive integer p > 1 is prime if its only divisors are 1 and itself. All integers > 1 are either prime or can be uniquely factored into primes.
Every integer n > 1 has a unique prime factorization: n = p₁^e₁ · p₂^e₂ · ... · pₖ^eₖ where p₁ < p₂ < ... < pₖ are primes and eᵢ ≥ 1.
Two integers a and b are relatively prime (or coprime) if gcd(a, b) = 1. For example, gcd(35, 64) = 1, so 35 and 64 are coprime.
§ 7.3 — Greatest Common Divisor (GCD)
3. Greatest Common Divisor (GCD)
The Greatest Common Divisor of two non-negative integers a and b, denoted gcd(a, b), is the largest integer that divides both a and b.
gcd(a, b) = max { k : k | a and k | b }. By convention, gcd(a, 0) = gcd(0, a) = a, and gcd(0, 0) = 0.
Properties of GCD
- Commutative: gcd(a, b) = gcd(b, a)
- Associative: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)
- gcd(a, b) = gcd(b, a mod b) — the key recursive property
- If d = gcd(a, b), then d | a and d | b
- gcd(ka, kb) = k · gcd(a, b) for any k > 0
- gcd(a, b) · lcm(a, b) = a · b
§ 7.4 — Euclid's Algorithm
4. Euclid's Algorithm
Euclid's algorithm efficiently computes gcd(a, b) using the key insight:
gcd(a, b) = gcd(b, a mod b), for any integers a ≥ b > 0.
This works because any common divisor of a and b also divides a mod b = a − ⌊a/b⌋·b. The base case is gcd(a, 0) = a.
EUCLID(a, b):
if b == 0
return a // base case
else
return EUCLID(b, a mod b) // recursive step
# Python Version ---------------------------------
def gcd_recursive(a, b):
if b == 0: return a
return gcd_recursive(b, a % b)
def gcd_iterative(a, b):
while b != 0:
a, b = b, a % b
return a
Step-by-Step Trace: gcd(252, 105)
| Call | a | b | a mod b | Next call |
|---|---|---|---|---|
| 1 | 252 | 105 | 42 | gcd(105, 42) |
| 2 | 105 | 42 | 21 | gcd(42, 21) |
| 3 | 42 | 21 | 0 | gcd(21, 0) |
| 4 | 21 | 0 | — | return 21 ✓ |
§ 7.5 — Extended Euclidean Algorithm
5. Extended Euclidean Algorithm
The Extended Euclidean Algorithm not only computes gcd(a, b) but also finds integers x and y (called Bézout coefficients) such that:
ax + by = gcd(a, b), where x and y are integers (possibly negative). These coefficients are critical for computing modular inverses.
EXTENDED-EUCLID(a, b):
if b == 0
return (a, 1, 0) // d=a, x=1, y=0
else
(d', x', y') = EXTENDED-EUCLID(b, a mod b)
(d, x, y) = (d', y', x' - ⌊a/b⌋ · y')
return (d, x, y)
# Python Version ---------------------------------
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
d, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return d, x, y
# Example: 35x + 15y = gcd(35, 15)
d, x, y = extended_gcd(35, 15) # d=5, x=1, y=-2
# 35×1 + 15×(−2) = 35 − 30 = 5 ✓
Application: Modular Inverse
If gcd(a, n) = 1, then the modular inverse of a modulo n is the value x returned by Extended-GCD(a, n), since ax ≡ 1 (mod n).
def mod_inverse(a, n):
d, x, _ = extended_gcd(a, n)
if d != 1: raise ValueError("Inverse doesn't exist")
return x % n
print(mod_inverse(3, 7)) # → 5, since 3×5 = 15 ≡ 1 (mod 7)
§ 7.6 — Definition of x modulo n
6. Definition of x modulo n
For integers a and n with n > 0, the expression a mod n denotes the unique remainder r such that a = qn + r and 0 ≤ r < n, where q = ⌊a/n⌋. We say a is congruent to b modulo n, written a ≡ b (mod n), if n | (a − b).
Properties of Modular Arithmetic
| Property | Formula | Example (mod 7) |
|---|---|---|
| Addition | (a + b) mod n = ((a mod n) + (b mod n)) mod n | (10 + 11) mod 7 = 0 |
| Subtraction | (a − b) mod n = ((a mod n) − (b mod n)) mod n | (10 − 3) mod 7 = 0 |
| Multiplication | (a × b) mod n = ((a mod n) × (b mod n)) mod n | (4 × 5) mod 7 = 6 |
| Reflexivity | a ≡ a (mod n) | 9 ≡ 9 (mod 7) |
| Symmetry | a ≡ b ↔ b ≡ a (mod n) | 9 ≡ 2 ↔ 2 ≡ 9 |
| Transitivity | a ≡ b, b ≡ c → a ≡ c (mod n) | — |
Residue Classes (Zₙ)
The set Zₙ = {0, 1, 2, ..., n−1} is called the complete residue system modulo n. Every integer belongs to exactly one residue class.
§ 7.7 — Solving Modular Linear Equations
7. Solving Modular Linear Equations
We want to solve the equation ax ≡ b (mod n) for unknown x. This has a solution if and only if d | b where d = gcd(a, n).
The equation ax ≡ b (mod n) has a solution x ∈ Zₙ if and only if d | b, where d = gcd(a, n). If solutions exist, there are exactly d distinct solutions modulo n.
Algorithm to Solve ax ≡ b (mod n)
- Compute d = gcd(a, n) using Extended-GCD(a, n). Get Bézout coefficients x₀, y₀.
- Check if d | b. If not, no solution exists.
- One solution is: x' = x₀ · (b/d) mod n
- All d solutions are: xᵢ = (x' + i · (n/d)) mod n for i = 0, 1, ..., d−1
def modular_linear_eq(a, b, n):
d, x0, _ = extended_gcd(a, n)
if b % d != 0: return []
x_prime = (x0 * (b // d)) % n
solutions = [(x_prime + i * (n // d)) % n for i in range(d)]
return sorted(solutions)
print(modular_linear_eq(14, 30, 100)) # → [45, 95]
Step 1: d = gcd(14, 100) = 2 Step 2: Does 2 | 30? Yes → solutions exist Step 3: Extended-GCD(14, 100) gives x₀ = −7 (so 14×(−7) + 100×1 = 2) Step 4: x' = (−7 × 15) mod 100 = −105 mod 100 = 45 Step 5: Two solutions: x₀ = 45, x₁ = (45 + 50) mod 100 = 95 ✓ Verify: 14×45 = 630 ≡ 30 (mod 100), 14×95 = 1330 ≡ 30 (mod 100)
§ 7.8 — Chinese Remainder Theorem (CRT)
8. Chinese Remainder Theorem (CRT)
The Chinese Remainder Theorem (CRT) provides an efficient way to solve systems of simultaneous congruences with pairwise coprime moduli.
Let n₁, n₂, ..., nₖ be pairwise coprime integers, and N = n₁·n₂·...·nₖ. For any integers a₁, a₂, ..., aₖ, the system x ≡ aᵢ (mod nᵢ) has a unique solution x modulo N.
Constructive Proof / Algorithm
- Compute N = n₁ · n₂ · ... · nₖ
- For each i, compute Nᵢ = N / nᵢ
- For each i, compute yᵢ = Nᵢ⁻¹ mod nᵢ (modular inverse)
- The solution is: x = (Σ aᵢ · Nᵢ · yᵢ) mod N
def crt(remainders, moduli):
N = 1
for m in moduli: N *= m
x = 0
for ai, ni in zip(remainders, moduli):
Ni = N // ni
yi = mod_inverse(Ni, ni)
x += ai * Ni * yi
return x % N
# Solve: x ≡ 2(mod 3), 3(mod 5), 2(mod 7)
print(crt([2, 3, 2], [3, 5, 7])) # → 23
N = 3 × 5 × 7 = 105 N₁ = 105/3 = 35, y₁ = 35⁻¹ mod 3 = 2 (35×2=70 ≡ 1 mod 3) N₂ = 105/5 = 21, y₂ = 21⁻¹ mod 5 = 1 (21×1=21 ≡ 1 mod 5) N₃ = 105/7 = 15, y₃ = 15⁻¹ mod 7 = 1 (15×1=15 ≡ 1 mod 7) x = (2×35×2 + 3×21×1 + 2×15×1) mod 105 = (140 + 63 + 30) mod 105 = 233 mod 105 = 23 ✓ Verify: 23 mod 3 = 2, 23 mod 5 = 3, 23 mod 7 = 2
Summary: Complexity
| Algorithm | Time Complexity | Space | Key Use |
|---|---|---|---|
| Euclid's GCD | O(log min(a,b)) | O(log n) / O(1) | Computing GCD |
| Extended Euclid | O(log min(a,b)) | O(log n) | Modular inverse, Bézout |
| Modular Linear Eq. | O(log n) | O(log n) | Solving ax ≡ b mod n |
| CRT | O(k · log N) | O(k) | k simultaneous congruences |