Lý thuyết số & số học đồng dư: bài tập có lời giải từng bước

1Số dư và đồng dư

Chia a cho n cho ta thương q và số dư r: a = q·n + r với 0 ≤ r < n. Số dư được viết là a mod n. Với một số âm, q cũng âm: −3 = −1·7 + 4, nên −3 mod 7 = 4.

Hai số đồng dư theo modulo n, a ≡ b (mod n), khi chúng có cùng số dư, tức là khi n chia hết a − b.

Số dư có thể được rút gọn ở mỗi bước, giúp giữ các số nhỏ:

Ví dụ 47·58 mod 9: 47 ≡ 2 và 58 ≡ 4, nên 47·58 ≡ 8 (mod 9).

2Thuật toán Euclid

Ước chung lớn nhất gcd(a, b) là số lớn nhất chia hết cho cả hai. Thuật toán Euclid dùng gcd(a, b) = gcd(b, a mod b):

1. Chia: a = q·b + r.
2. Thay (a, b) bằng (b, r).
3. Lặp lại cho đến khi số dư bằng 0. Số dư khác 0 cuối cùng là ước chung lớn nhất.

Bội chung nhỏ nhất suy ra từ đó: lcm(a, b) = a·b / gcd(a, b).

3Nghịch đảo và thuật toán mở rộng

Nghịch đảo của a theo modulo n là số x thỏa a·x ≡ 1 (mod n). Nó tồn tại đúng khi gcd(a, n) = 1.

Thuật toán Euclid mở rộng chạy Euclid trên (n, a) và giữ một hệ số t cho mỗi số dư, sao cho mọi số dư r ≡ t·a (mod n). Bắt đầu với t = 0 cho n và t = 1 cho a; mỗi t mới bằng t ở hai hàng trên trừ q nhân t ở một hàng trên. Khi số dư 1 xuất hiện, t của nó là số nghịch đảo.

Với số nghịch đảo, đồng dư a·x ≡ b (mod n) được giải bằng x ≡ a⁻¹·b. Khi d = gcd(a, n) lớn hơn 1, có d nghiệm nếu d chia hết b, và không có nghiệm nào nếu ngược lại.

Hai đồng dư với các modulo nguyên tố cùng nhau, x ≡ r₁ (mod m₁) và x ≡ r₂ (mod m₂), có đúng một nghiệm theo modulo m₁·m₂ (định lý số dư Trung Hoa). Viết x = r₁ + m₁k và giải tìm k.

4Lũy thừa modulo và RSA

Bình phương lặp tính aᵏ mod n nhanh: viết k ở dạng nhị phân, tìm a, a², a⁴, a⁸, … mod n bằng cách bình phương và rút gọn, rồi nhân các lũy thừa có bit bằng 1.

Định lý Fermat nhỏ: với số nguyên tố p không chia hết a, aᵖ⁻¹ ≡ 1 (mod p). Vì vậy số mũ có thể được rút gọn theo modulo p − 1.

RSA tạo một khóa từ hai số nguyên tố p và q:

1. n = p·q và φ(n) = (p − 1)(q − 1).
2. Chọn e với gcd(e, φ(n)) = 1; (n, e) là khóa công khai.
3. Tính d = e⁻¹ mod φ(n): khóa riêng.
4. Mã hóa c = mᵉ mod n; giải mã m = cᵈ mod n.

φ(n) của Euler đếm các số từ 1 đến n nguyên tố cùng nhau với n: φ(p) = p − 1 với số nguyên tố, φ(pᵏ) = pᵏ − pᵏ⁻¹, và φ có tính nhân với các thừa số nguyên tố cùng nhau.

5Lỗi thường gặp

• Cho số dư âm với một số âm: −17 mod 5 là 3, không phải −2.
• Dừng Euclid ở số dư đầu tiên thay vì số dư khác 0 cuối cùng.
• Quên cộng n vào một hệ số âm từ thuật toán mở rộng.
• Tính số mũ RSA d theo modulo n thay vì theo modulo φ(n).
• Rút gọn số mũ theo modulo p thay vì p − 1 khi dùng định lý Fermat.

6Các câu hỏi thi trông như thế nào

• Dễ: ước chung lớn nhất và số dư. Bạn chạy thuật toán Euclid để tìm gcd hoặc lcm, tìm số dư của số âm, và rút gọn tổng và tích theo modulo n.
• Trung bình: nghịch đảo và đồng dư. Bạn tìm nghịch đảo modulo bằng thuật toán mở rộng, giải đồng dư tuyến tính, kết hợp hai đồng dư bằng định lý số dư Trung Hoa, và tính φ(n) của Euler.
• Khó: lũy thừa modulo và RSA. Bạn dùng bình phương lặp và định lý Fermat, giải các đồng dư có nhiều nghiệm, và tìm số mũ bí mật RSA, bản mã và thông điệp đã giải mã.