Mod trong toán học là gì
Modulo số học (Modular Arithmetic) và số nguyên tố là nền tảng toán học cơ bản trong mật mã học. Ta thường quan tâm đến các phép chia hết như 4:2=2, vậy bạn có bao giờ tự hỏi 10000000000000 chia 7 còn bao nhiêu không? Show Phép chia Modulo (Modulo Operator)Phép chia lấy dư (chia modulo) ký hiệu là mod hay % (trong lập trình) cho đáp án là phần dư của phép tính chia. Ví dụ: 5 chia 2 được 2 dư 1. Ta có: Ta có a ≡ b (mod n) nếu a = b + kn, trong đó k là một số nguyên. Nếu a và b dương và a nhỏ hơn n, chúng ta có thể gọi a là phần dư của b khi chia cho n. Nói chung a và b đều là phần dư khi chia cho n. Người ta gọi b là thặng dư của a theo modulo n, và a là đồng dư của b theo modulo n. Phép so sánh đồng dư được ký hiệu bằng dấu ≡ a ≡ b (mod n) hay viết thành a ≡ b mod n Ví dụ:
Một số tính chất của phép moduloModulo số học cũng như số học bình thường, bao gồm các phép giao hoán, kết hợp và phân phối. Mặt khác giảm mỗi giá trị trung gian trong suốt quá trình tính toán. Cho a, b và n là các số nguyên, phép modulo có các tính chất:
Vì quan hệ đồng dư là quan hệ tương đương, nên ta có các tính chất từ quan hệ tương đương:
Nếu a1 ≡ b1 (mod n) và a2 ≡ b2 (mod n), hoặc a ≡ b (mod n), thì:
Nếu a ≡ b (mod n), ta thường dễ nhầm cho rằng ka ≡ kb (mod n). Tuy nhiên điều sau là đúng:
Đối với việc loại bỏ phần tử ở hai bên, ta có các luật sau:
Các phép tính trong các hệ mật mã hầu hết đều tính theo một modulo N nào đó. Ví dụ: Áp dụng các tính chất của Modulo số học, tính:
(11 * 19 + 1017) mod 7 \= ((11 * 19 mod 7) + 1017 mod 7) mod 7 \= ((11 mod 7 * 19 mod 7) mod 7 + (10 mod 7)17) mod 7 \= (( 4 * 5 ) mod 7 + (3 mod 7)17) mod 7 \= (6 mod 7 + (((98) mod 7) * 3 mod 7) mod 7)) mod 7 \= (6 mod 7 + ((28 mod 7) * 3 mod 7)) mod 7 \= (6 mod 7 + ((4*3) mod7)) mod 7 \= (6 + 5) mod 7 \= 11 mod 7 \= 4 Bài tậpTính giá trị các biểu thức sau theo modulo
Ước số chungNếu a mod n = 0 (viết cách khác a ≡ 0 mod n ) thì có nghĩa là a chia hết cho n, hay n là ước số của a. Ước số chung lớn nhất của hai số: ký hiệu gcd(a, b). Để tìm USCLN của hai số a, b, chúng ta có thể dùng thuật toán Euclid ở bài sau. Số nguyên tốMột số p được gọi là số nguyên tố nếu p chỉ chia hết cho 1 và chính nó, ngoài ra không chia hết cho số nào khác từ 2 đến p – 1. Số 2 là một số nguyên tố đầu tiên và là số nguyên tố chẵn duy nhất . Do vậy 7, 17, 53, 73, 2521, 2365347734339 cũng là số nguyên tố. Số lượng số nguyên tố là vô tận . Hệ mật mã thường sử dụng số nguyên tố cỡ 512 bits và thậm chí lớn hơn như vậy. Số nguyên tố cùng nhauHai số nguyên a, b được gọi là nguyên tố cùng nhau nếu USCLN của a và b là 1. Ký hiệu: a⊥b. Ví dụ: 3 ⊥ 8, 7 ⊥ 9, 4 ⊥ 15. Hai số 20 và 15 không nguyên tố cùng nhau vì có USCLN là 5. Vành ZN (vành đồng dư Modulo N)Tập các số nguyên ZN = {0, 1, 2, …, N-1} trong đó N là một số tự nhiên dương với hai phép toán cộng (+) và nhân (.) được định nghĩa như sau:
Theo tính chất của modulo số học ta dễ dàng nhận thấy ZN là một vành giao hoán kết hợp. Hầu hết các tính toán trong các hệ mã mật đều được thực hiện trên một vành ZN nào đó. Trên vành ZN:
Ví dụ: Với N = 9
Phần tử nghịch đảo trên vành ZnTrên trường số thực R, số nghịch đảo của 5 mà 1/5 bởi vì 5 × 1/5 = 1. Còn trên vành số nguyên ZN người ta đưa ra khái niệm về số nghịch đảo của một số như sau: Giả sử a ∈ ZN và tồn tại b ∈ ZN sao cho a.b = (a*b) mod N = 1. Khi đó b được goi là phần tử nghịch đảo của a trên ZN và ký hiệu là a-1 = b. Việc tìm phần tử nghịch đảo của một số a ∈ ZN cho trước thực chất tương đương với việc tìm hai số b và k sao cho: a.b = k.N + 1, trong đó b, k ∈ ZN. Hay viết gọn lại là: a-1 ≡ b (mod N) Định lý về sự tồn tại của phần tử nghịch đảo: Nếu GCD(a, N) = 1 thì tồn tại duy nhất 1 số b ∈ ZN là phần tử nghịch đảo của a, nghĩa là thoả mãn a.b = (a*b) mod N = 1. Để tìm được phần tử nghịch đảo a-1 mod N, ta sử dụng thuật toán Euclid mở rộng sẽ được đề cập chi tiết trong bài sau. |