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