Number-Theoretic Algorithms for Cryptography & Modular Arithmetic | Chapter 31 in Introduction to Algorithms

Chapter 31 of Introduction to Algorithms explores foundational number-theoretic algorithms that power modern cryptography, modular arithmetic, and primality testing. From computing greatest common divisors to understanding public-key encryption like RSA, this chapter equips readers with the mathematical tools that underpin secure communication and cryptographic protocols.

Watch the video above for a guided podcast-style summary of the chapter, and subscribe to Last Minute Lecture for more algorithm-focused textbook breakdowns every week.

Core Number-Theoretic Concepts

The chapter begins by reviewing the basics of number theory:

• Divisibility: d divides a if a = kd for some integer k
• Primes: Only divisible by 1 and themselves
• Greatest Common Divisor (gcd): The largest integer dividing two numbers
• Modular Equivalence: a ≡ b (mod n) if a and b have the same remainder when divided by n
• Relatively Prime: Two numbers with gcd equal to 1
• Unique Prime Factorization: Every integer greater than 1 is a product of primes

Euclidean and Extended Euclidean Algorithms

The Euclidean algorithm efficiently computes the gcd of two integers using recursive division: gcd(a, b) = gcd(b, a mod b). Its extended form not only finds the gcd but also integers x and y such that:

ax + by = gcd(a, b)

This result is crucial for calculating modular inverses, which are necessary for RSA key generation and solving modular equations.

Modular Arithmetic and Group Theory

Modular arithmetic defines operations under a fixed modulus n:

• Additive group mod n (ℤₙ): Contains integers {0, 1, ..., n–1} under addition mod n
• Multiplicative group mod n (ℤₙ*): Elements relatively prime to n under multiplication mod n
• Euler’s Phi Function (φ(n)): Counts integers ≤ n that are coprime to n

Group theory concepts like subgroups, generated elements, and Lagrange’s theorem provide structure for understanding modular systems.

Solving Modular Linear Equations

To solve equations of the form ax ≡ b mod n:

• The number of solutions equals d = gcd(a, n), assuming d divides b.
• If a and n are coprime, there’s a unique solution using the extended Euclidean algorithm.

This method is a building block in modular systems and cryptographic calculations.

Chinese Remainder Theorem (CRT)

The CRT helps solve simultaneous congruences:

x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), ..., x ≡ aₖ (mod nₖ)

If the moduli are pairwise relatively prime, there’s a unique solution modulo N = n₁ × n₂ × ... × nₖ. CRT is widely used in RSA decryption to speed up computations using smaller moduli.

Euler’s Theorem, Fermat’s Theorem, and Primitive Roots

• Euler’s Theorem: If gcd(a, n) = 1, then a^φ(n) ≡ 1 mod n
• Fermat’s Theorem: If p is prime, then a^(p–1) ≡ 1 mod p for a ≠ 0 mod p

These theorems form the mathematical foundation of modular exponentiation and RSA encryption. The chapter also introduces primitive roots and the discrete logarithm problem, both essential in understanding cyclic groups and cryptographic hardness assumptions.

Modular Exponentiation

This algorithm computes a^b mod n efficiently using repeated squaring. It runs in Θ(log b) time and is critical in public-key systems like RSA for fast encryption and decryption.

RSA Cryptosystem

The RSA algorithm is detailed as a real-world application of number-theoretic principles:

1. Choose two large primes p and q
2. Compute n = pq and φ(n) = (p–1)(q–1)
3. Select public exponent e such that gcd(e, φ(n)) = 1
4. Find d such that ed ≡ 1 mod φ(n)

Encryption: C = M^e mod n Decryption: M = C^d mod n

The correctness of RSA is grounded in Euler’s theorem and CRT. Security relies on the computational difficulty of factoring large numbers.

Primality Testing

Several methods for testing primality are introduced:

• Trial Division: Simple but slow
• Pseudoprime Test: a^(n–1) ≡ 1 mod n may fail for Carmichael numbers
• Miller-Rabin Test: A probabilistic test with high confidence; runs multiple rounds to reduce the chance of error to 2^(–s)

These tests are crucial for generating large primes in RSA key generation and other cryptographic protocols.

Conclusion

Chapter 31 provides the mathematical scaffolding for many essential cryptographic and number-theoretic tools. Understanding Euclidean algorithms, modular systems, and primality tests equips you to analyze and implement secure algorithms in both academic and applied contexts.

🎓 To solidify your understanding of modular arithmetic and RSA encryption, watch the full breakdown above and explore more chapters on the Last Minute Lecture channel.

If you found this breakdown helpful, be sure to subscribe to Last Minute Lecture for more chapter-by-chapter textbook summaries and academic study guides.