Lesson 04 — Modular Arithmetic & GCD

Bốn công cụ tương tác: đồng hồ modular, thuật toán Euclid tìm GCD từng bước, lũy thừa modular nhanh (square-and-multiply), và bộ tìm nghịch đảo modular.

1. Đồng hồ modular — (a op b) mod m

Kim quay từ 0, đi a bước rồi cộng/nhân với b; kết quả gập về vòng m vạch. Đây là trực giác "đếm trên vòng tròn".

2. Euclid GCD stepper — gcd(a,b) = gcd(b, a mod b)

Mỗi bước thay cặp (a,b) bằng (b, a mod b) tới khi số thứ hai bằng 0. Số bước ≈ O(log).

3. Fast modular exponentiation — a^b mod m

Square-and-multiply: duyệt từng bit của b, bình phương base mỗi vòng, bit = 1 thì nhân vào kết quả. O(log b) phép nhân.

4. Modular inverse finder — a⁻¹ mod m

Tìm x sao cho a·x ≡ 1 (mod m) bằng Extended Euclid. Tồn tại ⇔ gcd(a, m) = 1.