Máy Tính Số Học Modulo

Tính toán các phép toán số học modulo bao gồm chia lấy dư, nghịch đảo modulo và lũy thừa modulo cho mật mã học và lý thuyết số.

Số học modulo là gì?

Số học modulo là hệ thống số học cho các số nguyên trong đó các số "quay vòng" sau khi đạt đến một giá trị nhất định (modulo). Nó thường được mô tả là "số học đồng hồ."

Biểu thức a mod m cho số dư khi a chia cho m. Ví dụ, 17 mod 5 = 2 vì 17 = 3 × 5 + 2.

Các phép toán cơ bản

Số học modulo hỗ trợ tất cả các phép toán cơ bản:

• Phép cộng: (a + b) mod m = ((a mod m) + (b mod m)) mod m
• Phép trừ: (a - b) mod m = ((a mod m) - (b mod m)) mod m
• Phép nhân: (a × b) mod m = ((a mod m) × (b mod m)) mod m

Lũy thừa Modulo

Lũy thừa modulo tính a^b mod m một cách hiệu quả bằng thuật toán bình phương và nhân. Điều này rất quan trọng cho mã hóa RSA.

Ví dụ, 3^5 mod 7 = 243 mod 7 = 5.

Nghịch đảo Modulo

Nghịch đảo modulo của a theo modulo m là số x sao cho:

a × x ≡ 1 (mod m)

Nghịch đảo modulo chỉ tồn tại khi a và m nguyên tố cùng nhau (gcd(a, m) = 1). Nó được tính bằng thuật toán Euclid mở rộng.

Ví dụ, nghịch đảo của 3 mod 7 là 5, vì 3 × 5 = 15 ≡ 1 (mod 7).

Ứng dụng của số học modulo

Số học modulo là nền tảng trong nhiều lĩnh vực:

• Mật mã học: Mã hóa RSA, trao đổi khóa Diffie-Hellman
• Khoa học máy tính: Hàm băm, checksum, sinh số ngẫu nhiên
• Lý thuyết số: Kiểm tra số nguyên tố, thuật toán phân tích
• Lý thuyết mã hóa: Mã phát hiện và sửa lỗi
• Lý thuyết âm nhạc: Kỹ thuật mười hai âm và lớp cao độ
• Tính toán lịch: Thuật toán tính ngày trong tuần

Vì sao 17 mod 5 = 2 chứ không phải -3?

Hai đáp án đều đúng về mặt toán học vì 2 và -3 chênh nhau đúng 5 (modulo), nên cùng đại diện một lớp tương đương modulo 5. Quy ước trong công cụ này — và trong toán học, khoa học máy tính, mật mã học — là trả số dư không-âm: số r nhỏ nhất thỏa 0 ≤ r < m. Vậy 17 mod 5 trả 2 (vì 17 = 3 × 5 + 2), và -3 mod 5 cũng trả 2 (vì -3 = -1 × 5 + 2). Đây gọi là modulo "Euclid" hoặc "floor". Một số ngôn ngữ lập trình (C, Java, JavaScript với %) dùng modulo "truncated" giữ dấu của số bị chia — nên JavaScript -3 % 5 trả -3, không phải 2. Công cụ này dùng quy ước toán học vì nó không mơ hồ và khớp với mọi giáo trình lý thuyết số và mật mã.

Khi nào nghịch đảo modulo tồn tại?

Nghịch đảo a⁻¹ mod m tồn tại khi và chỉ khi gcd(a, m) = 1, tức a và m nguyên tố cùng nhau (không chia sẻ ước chung nào khác 1). Ví dụ: 3 mod 7 — gcd(3, 7) = 1, có nghịch đảo, là 5 (vì 3 × 5 = 15 ≡ 1 mod 7). Ví dụ: 6 mod 9 — gcd(6, 9) = 3, không có nghịch đảo. Tính bằng thuật toán Euclid mở rộng, tạo ra cả gcd lẫn nghịch đảo đồng thời. Điều kiện này quan trọng với RSA: số mũ mã hóa e và hàm Euler φ(n) phải nguyên tố cùng nhau, nếu không khóa riêng không thể suy ra. Công cụ này báo "không có nghịch đảo" khi gcd > 1, thay vì âm thầm cho đáp án sai.

Vì sao lũy thừa modulo quan trọng cho RSA?

Mã hóa RSA tính c = m^e mod n, với m là bản rõ, e là số mũ công khai (thường 65537), n là modulus công khai (thường 2048 hoặc 4096 bit). Với n 2048 bit, giá trị có thể dài hàng trăm chữ số. Tính m^e trước rồi mới mod n là bất khả thi — giá trị trung gian sẽ lớn thiên văn, không máy tính nào lưu nổi. Thuật toán bình phương-và-nhân (modular exponentiation by repeated squaring) đan xen bình phương với rút gọn modulo n, giữ mọi giá trị trung gian nhỏ hơn n. Với e = 65537 = 2^16 + 1, chỉ cần 17 phép nhân modulo thay vì 65536 — tăng tốc khoảng 4000 lần. Các thư viện mật mã an toàn còn thêm cài đặt thời gian-hằng để chống tấn công timing.

Khác biệt giữa a mod m và a % m trong lập trình là gì?

Không giống nhau. Modulo toán học (a mod m) luôn trả kết quả không-âm với m dương: 0 ≤ result < m. Toán tử % trong lập trình phụ thuộc ngôn ngữ. C, C++, Java, JavaScript, Go: modulo truncated — dấu khớp với số bị chia, nên -7 % 3 trả -1. Python: modulo floor — dấu khớp với số chia, nên -7 % 3 trả 2. Quy ước toán học: -7 mod 3 = 2 (khớp Python). Khi chuyển code mật mã hoặc lý thuyết số từ nguồn toán sang JavaScript hoặc C, phải xử lý trường hợp âm thủ công: ((a % m) + m) % m cho kết quả toán học đúng bất kể dấu. Công cụ này dùng quy ước toán học nên kết quả khớp giáo trình lý thuyết số bất kể nền lập trình của người dùng.

Vì sao số học modulo còn gọi là "số học đồng hồ"?

Vì mặt đồng hồ là ví dụ quen thuộc nhất. Đồng hồ 12 giờ hoạt động theo modulo 12: 11 giờ + 4 giờ = 3 giờ, vì 11 + 4 = 15, và 15 mod 12 = 3. Thời gian "quay vòng" qua modulo y như số học modulo. Đồng hồ quân đội 24 giờ chạy modulo 24, lịch theo ngày trong tuần modulo 7, góc modulo 360 độ (hoặc 2π radian). Bất cứ khi nào có đại lượng tuần hoàn — góc, ngày, giờ, lớp cao độ âm nhạc, giá trị màu sắc — số học modulo là khung tự nhiên. Ẩn dụ đồng hồ được phổ biến trong tác phẩm Disquisitiones Arithmeticae 1801 của Gauss, công trình nền tảng của số học modulo, nơi ông giới thiệu ký hiệu đồng dư ≡ mà ta vẫn dùng.

Modulus có thể âm hoặc bằng 0 không?

Bằng 0 thì không bao giờ — chia cho 0 là không xác định, a mod 0 vô nghĩa. Công cụ này từ chối modulus = 0 và báo lỗi. Modulus âm về toán học được phép nhưng theo quy ước coi như dương (-5 tương đương +5 làm modulus, vì các lớp tương đương giống nhau). Để kết quả dễ đoán, công cụ này yêu cầu modulus là số nguyên dương ≥ 1. Lưu ý: mod 1 là trường hợp đặc biệt — mọi số nguyên đều đồng dư 0 — hữu ích trong chứng minh nhưng tầm thường trong tính toán. Hầu hết ứng dụng thực tế dùng m ≥ 2.

Định lý nhỏ Fermat là gì và liên quan thế nào?

Định lý nhỏ Fermat phát biểu: nếu p là số nguyên tố và a là số nguyên không chia hết p, thì a^(p-1) ≡ 1 (mod p). Đây là nền tảng cho nhiều thứ: (1) Kiểm tra nguyên tố — nếu tìm được a sao cho gcd(a, n) = 1 nhưng a^(n-1) ≢ 1 mod n, thì n chắc chắn là hợp số. Miller-Rabin là phiên bản tinh chỉnh của kiểm tra này. (2) Tạo khóa RSA — định lý này khiến giải mã RSA hoạt động; toán dựa trên a^(φ(n)) ≡ 1 mod n, mở rộng Fermat qua định lý Euler cho n không nguyên tố. (3) Mật mã logarit rời rạc — nhiều giao thức dựa vào việc số mũ rút gọn modulo p-1 khi cơ số nằm trong nhóm nhân mod p. Thử: 2^6 mod 7 = 64 mod 7 = 1 (vì 7 nguyên tố và gcd(2,7)=1).

Công cụ này có xử lý được số rất lớn dùng trong mật mã không?

Có với đầu vào kích thước thường (đến giới hạn số nguyên an toàn của JavaScript, 2^53 ≈ 9 × 10^15), nhưng không cho kích thước khóa mật mã đầy đủ (2048+ bit ≈ 600+ chữ số). Công cụ chạy trong trình duyệt bằng số JavaScript thông thường, mất chính xác trên 2^53. Để tính toán mật mã thực, các thư viện dùng số nguyên độ chính xác tùy ý qua BigInt (có sẵn trong trình duyệt hiện đại) — mở console trình duyệt và thử (3n ** 5n) % 7n cho số học BigInt. Cho việc dùng hàng ngày — bài tập lý thuyết số, phân tích hàm băm, tính lịch, demo RSA khóa nhỏ — độ chính xác của công cụ này quá đủ. Cho mã hóa thực, dùng thư viện được kiểm chứng như OpenSSL hoặc libsodium, đừng tự viết.