Bài 3: Modulo số học – Phép chia lấy dư – Ước số chung lớn nhất – Vành Zn

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?

Phép chia lấy dư

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ụ:

• 42 = 6+4×9, vậy 42 ≡ 6 (mod 9)
• -42 = -6 + -4×9 vậy -42 ≡ -6 (mod 9) Tuy nhiên -6 ≡ -6 + 1×9 ≡ 3 (mod 9). Vậy nên -42 ≡ 3 (mod 9)

Một số tính chất của phép modulo

Modulo 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:

• (a+b) mod n = ((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) × (b mod n)) mod n
• (a×(b + c)) mod n = (((a × b) mod n) + ((a × c) mod n)) mod n

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:

• Phản xạ: a ≡ a (mod n)
• Đối xứng: a ≡ b (mod n) khi và chỉ khi b ≡ a (mod n) với mọi a, b
• Bắc cầu: nếu a ≡ b (mod n) và b ≡ c (mod n) thì a ≡ c (mod n)

Nếu a₁ ≡ b₁ (mod n) và a₂ ≡ b₂ (mod n), hoặc a ≡ b (mod n), thì:

• a + k ≡ b + k (mod n) với mọi số nguyên k
• k a ≡ k b (mod n) với mọi số nguyên k
• a₁ + a₂ ≡ b₁ + b₂ (mod n) (bảo toàn phép cộng)
• a₁ – a₂ ≡ b₁ – b₂ (mod n) (bảo toàn phép trừ)
• a₁ a₂ ≡ b₁ b₂ (mod n) (bảo toàn phép nhân)
• a^k ≡ b^k (mod n) với mọi số nguyên không âm k (bảo toàn phép mũ)
• p(a) ≡ p(b) (mod n), với mọi đa thức p(x) có hệ số nguyên (bảo toàn với đa thức)

Nếu a ≡ b (mod n), ta thường dễ nhầm cho rằng k^a ≡ k^b (mod n). Tuy nhiên điều sau là đúng:

• Nếu c ≡ d (mod φ(n)), với φ is Hàm phi euler, thì a^c ≡ a^d (mod n)— nếu như a nguyên tố cùng nhau với n.

Đối với việc loại bỏ phần tử ở hai bên, ta có các luật sau:

• Nếu a + k ≡ b + k (mod n), với k là số nguyên bất kì, thì a ≡ b (mod n)
• Nếu k a ≡ k b (mod n) và k nguyên tố cùng nhau với n, thì a ≡ b (mod n)
• Nếu k a ≡ k b (mod kn) , thì a ≡ b (mod n)

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:

• (14 + 7) mod 15 → (21) mod 15 = 6
• (7 − 11) mod 13 → (−4) mod 13 = 9
• (7 × 11) mod 20 → (77) mod 20 = 17
• (12 + 18) mod 7 = (12 mod 7 + 18 mod 7) mod 7 = 2
• (12 × 18) mod 7 = (12 mod 7 * 18 mod 7) mod 7 = (5*4) mod 7 = 20 mod 7 = 6

(11 * 19 + 10¹⁷) mod 7

= ((11 * 19 mod 7) + 10¹⁷ mod 7) mod 7
= ((11 mod 7 * 19 mod 7) mod 7 + (10 mod 7)¹⁷) mod 7
= ((      4        *       5       ) mod 7 + (3   mod 7)¹⁷) mod 7
= (6 mod 7 + (((9⁸) mod 7) * 3 mod 7) mod 7)) mod 7
= (6 mod 7 + ((2⁸ 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ập

Tính giá trị các biểu thức sau theo modulo

1. 8 + 7 (mod 9)
2. 8 mod 9 * 7 mod 9
3. 5 mod 11 – 9 mod 11
4. 5³ mod 7
5. 5²⁰ mod 7

Ước số chung

Nế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 nhau

Hai 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 Z_N (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:

• Phép cộng: ∀ a,b ∈ Z_N: a+b=(a+b) mod N
• Phép nhân: ∀a,b ∈ Z_N: a∙b=(a*b) mod N

Theo tính chất của modulo số học ta dễ dàng nhận thấy Z_N 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 Z_N nào đó.

Trên vành Z_N:

• Số 0 là phần tử trung hoà vì: a + 0 = 0 + a = a với ∀ a ∈ Z_N
• Số 1 được gọi là phần tử đơn vị vì: a.1 = 1.a = a với ∀ a ∈ Z_N

Ví dụ: Với N = 9

• Z9 = {0, 1, 2, 3, 4, 5, 6, 7, 8}
• 6 + 8 = 14 ≡ 5 (mod 9)
• 6.8 = 48 ≡ 3 (mod 9)

Phần tử nghịch đảo trên vành Zn

Trê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 Z_N người ta đưa ra khái niệm về số nghịch đảo của một số như sau:

Giả sử a ∈ Z_N và tồn tại b ∈ Z_N 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 Z_N và ký hiệu là a^-1 = b.

Việc tìm phần tử nghịch đảo của một số a ∈ Z_N 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 ∈ Z_N. 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 ∈ Z_N 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.

Tài liệu tham khảo:

• [1] Bài giảng An toàn và bảo mật thông tin, Trường Đại học Nha Trang, Biên soạn Trần Minh Văn, 2008.
• [2] Giáo trình An toàn và bảo mật thông tin, Trường Đại học Hàng hải – Hải Phòng, 2008.
• [3] Tài liệu biên soạn và sưu tầm.

Nguồn: Nam.Name.Vn