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
—
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
3. Extended Euclidean — Tìm Modular Inverse
Tìm a⁻¹ mod n (= s trong as + nt = 1)
Thử: tìm nghịch đảo của 7 mod 26 — Extended Euclid lần ngược ra 15 vì 7·15 = 105 ≡ 1: đây chính là cách RSA tính khóa giải mã d.