Lesson 04: Modular Arithmetic Foundations

Nền tảng toán cho RSA: phép toán mod, Euclidean GCD, Extended Euclidean (modular inverse), Fermat's little theorem, Euler totient, và fast exponentiation.

1. Phép Toán Modular — Đồng hồ số học

Visualize a mod n trên đồng hồ tròn

Modulus n: Value a:

—

Thử phép tính:

mod

—

2. Euclidean Algorithm — Tính GCD từng bước

gcd(a, b) bằng phép chia liên tiếp

a = b =

3. Extended Euclidean — Tìm Modular Inverse

Tìm a⁻¹ mod n (= s trong as + nt = 1)

a = n =

4. Euler's Totient φ(n) — Bộ đếm coprime

Visualize φ(n) = số phần tử coprime với n

n =

5. Fast Exponentiation — Square-and-Multiply

Tính a^k mod n trong O(log k) bước

a = k = mod n =