Toán học modulo là cấu trúc số học cho số nguyên, nơi số "quay vòng" khi đạt giá trị cụ thể. Toán học modulo cho phép dễ dàng tạo nhóm, vòng, trường - các khối xây dựng cơ bản của hầu hết hệ mật mã khóa công khai hiện đại.
Ví dụ, Diffie-Hellman cần nhóm nhân số nguyên modulo số nguyên tố p. Có nhiều nhóm khác hoạt động. Toán học modulo hoặc đồng hồ là số học trên đường tròn thay vì đường số modulo N, chỉ dùng N số nguyên từ 0 đến N-1.
Toán học modulo được hiểu rõ về thuật toán các phép toán cơ bản. Đó là lý do dùng trường hữu hạn (AES) trong mật mã khóa đối xứng. Mật mã học cần bài toán phức tạp. Một số bài toán trở nên khó với toán học modulo.
Ví dụ, logarit dễ tính trên tất cả số nguyên nhưng trở nên khó khi đưa vào rút gọn modulo. Tương tự tìm căn. Toán modulo là thuật ngữ toán học trung tâm trong mật mã học.
Nhiều lý thuyết số hiện đại và bài toán thực tế liên quan đến toán học modulo. Trong số học modulo N, liên quan đến số học trên số nguyên, nơi nhận diện tất cả số khác nhau bội số cưỡng lại của N. Đó là,
x = y (mod N) nếu x = y + mN với m số nguyên.
Nhận diện này chia tất cả số nguyên thành N lớp tương đương. Thường ký hiệu bằng thành viên đơn giản nhất: 0, 1, ..., N-1.
Nếu a là số nguyên và n là số nguyên dương, ký hiệu a mod n là phần dư khi a chia cho n. Thì a = ⌊a/n⌋ x n + (a mod n).
Ví dụ: 11 mod 7 = 4
Định lý - n là quan hệ tương đương trên số nguyên. Lớp tương đương chứa các số nguyên có cùng phần dư chia cho n. Lớp tương đương cũng gọi là lớp đồng dư modulo n. Thay vì nói a và b tương đương, nói a và b đồng dư modulo n.
Tập tất cả số nguyên đồng dư với a modulo n gọi là lớp dư [a].
Toán tử modulo có các tính chất:
a ≡ b (mod n) nếu n | (a - b).
(a mod n) = (b mod n) ngụ ý a ≡ b (mod n).
a ≡ b (mod n) ngụ ý b ≡ a (mod n).
a ≡ b (mod n) và b ≡ c (mod n) ngụ ý a ≡ c (mod n).
Tính chất phép toán modulo
[(a mod n) + (b mod n)] mod n = (a + b) mod n
[(a mod n) - (b mod n)] mod n = (a - b) mod n
[(a mod n) x (b mod n)] mod n = (a x b) mod n
Để Zn = {0, 1, 2,... (n-1)}, là tập dư modulo n.
| Tính chất | Biểu thức |
|---|---|
| Luật giao hoán | (w + x) mod n = (x + w) mod n |
| Luật kết hợp | (w x x) mod n = (x x w) mod n |
| [(w + x)+y] mod n = [w+(x+y)] mod n | |
| Luật phân phối | [(w x x) x y] mod n = [w x (x x y)] mod n |
| Phần tử trung hòa | [(w x (x + y)] mod n =[(w x x) + (w x y)] mod n |
| (0 + w) mod n = w mod n | |
| Nghịch đảo cộng (-w) | (1 x w) mod n = w mod n |
| Với mỗi w ∈ Zn, tồn tại z sao cho w + z ≡ 0 (mod n) |