Máy tính modulo

Cộng, trừ, nhân, lũy thừa, nghịch đảo modulo. Tìm hiểu các phép toán mô-đun dùng trong mật mã RSA.

Modulo cơ bản — Cộng modulo — Trừ modulo — Nhân modulo — Lũy thừa modulo — Nghịch đảo modulo —

HƯỚNG DẪN

Tìm hiểu thêm

Kiến thức cơ bản về phép modulo

Phép modulo (a mod m) là phần dư khi a được chia cho m. Ví dụ: 17 mod 5 = 2. Được dùng hằng ngày trong tính toán đồng hồ (24 giờ), tính thứ trong tuần. Rất quan trọng trong lập trình để quấn chỉ số mảng, hàm băm.

Cộng và nhân modulo

Cộng modulo: (a + b) mod m. Nhân modulo: (a × b) mod m. Để tránh tràn số khi tính với số lớn, hãy lấy modulo ở mỗi bước. Ví dụ: (12 + 8) mod 5 = 20 mod 5 = 0.

Lũy thừa modulo - tính toán nhanh

Khi tính a^b mod m, phép lũy thừa trực tiếp làm số trở nên quá lớn. Dùng thuật toán lũy thừa nhanh chia để trị giúp tính trong thời gian O(log b). Đây là phép toán cốt lõi của mã hóa RSA.

Nghịch đảo modulo - thuật toán Euclid mở rộng

Nghịch đảo modulo là x sao cho (a × x) mod m = 1. Chỉ tồn tại khi a và m nguyên tố cùng nhau. Được tính trong thời gian O(log m) bằng thuật toán Euclid mở rộng. Dùng trong giải mã, tính toán phân số.

Mật mã RSA và các phép toán modulo

RSA là hệ mật mã khóa công khai dựa trên lũy thừa modulo và nghịch đảo. Mã hóa: c = m^e mod n, Giải mã: m = c^d mod n. Dựa vào độ khó phân tích n, tích của hai số nguyên tố lớn.

Câu hỏi thường gặp

Điều gì xảy ra khi tôi tính modulo với số âm?

Quy ước modulo âm khác nhau tùy ngôn ngữ, nhưng máy tính này theo định nghĩa toán học, trong đó kết quả luôn nằm giữa 0 và m-1. Ví dụ: -7 mod 5 = 3.

Nếu tôi nhập 0 làm mô-đun (m) thì sao?

Chia cho 0 là không xác định, nên không thể tính mô-đun bằng 0. Mô-đun m phải là số nguyên dương.

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

Nghịch đảo modulo chỉ tồn tại khi a và m nguyên tố cùng nhau, nghĩa là ước chung lớn nhất của chúng bằng 1. Ví dụ, nếu cả a và m đều chẵn thì không tồn tại nghịch đảo.

Vì sao cần thuật toán nhanh cho lũy thừa modulo?

Khi số mũ tăng, a^b trở nên cực kỳ lớn, khiến phép tính trực tiếp không khả thi. Lũy thừa nhanh (chia để trị) áp dụng modulo ở mỗi bước để giữ số nhỏ, và tính kết quả trong thời gian O(log b).

Số học mô-đun được dùng ở đâu trong thực tế?

Nó hỗ trợ xác định bucket trong bảng băm, lập lịch theo chu kỳ (ngày trong tuần, thời gian trên đồng hồ), mã hóa/giải mã trong RSA và các hệ khóa công khai khác, cùng xác thực checksum như kiểm tra ISBN.