Lý thuyết số Nhóm, vành, trường

Lý thuyết số Nhóm, vành, trường

Rate this post

Các thuật ngữ nhóm (group), vành (ring) và trường (field) cho phép ta xác định các phép toán trên tập các số nguyên:

Đĩnh nghĩa về nhóm(group), vành (ring) và trường (field)

Nhóm:

  • Là tập các số, có định nghĩa phép cộng và đóng đối với nó
  • Tuân thủ luật kết hợp, có bất biến, có nghịch đảo đối với phép cộng
  • Nếu có thêm luật giao hoán thì được gọi là nhóm Abel (abelian group) Ví dụ: Nhóm các số nguyên theo mod N: A={0, 1, …, N-1} là nhóm

Abel. Ta sẽ kiểm tra xem có thoả các tính chất của nhóm.

Tính đóng: Nếu x ∈ A, y ∈ A thì (x + y) mod N ∈ A. Luật kết hợp: ((x + y) + z) mod N = (x + (y + z)) mod N Bất biến là 0 vì: (x + 0) mod N = x mod N

Nghịch đảo: nghịch đảo của x ∈ A là (N – x) ∈ A vì a + (N – a) mod N

= 0 (Bất biến).

Luật giao hoán: (x + y) mod N = (y + x) mod N

Vành:

  • Là nhóm Abel cho phép cộng; có định nghĩa thêm phép nhân
  • Có luật kết hợp cho phép nhân và luật phân phối của phép nhân đối  với phép cộng
  • Nếu phép nhân có thêm luật giao hoán thì được gọi là vành giao hoán (commutative ring).

Ví dụ: Vành các số nguyên theo mod N: {0, 1, …, N-1}

Các bài viết liên quan:

Trường:

  • Là nhóm Abel cho phép cộng
  • Là 1 vành
  • Là nhóm Abel cho phép nhân (trừ phần tử 0).

Ví dụ: Trường các số nguyên theo mod N: {0, 1, …, N-1} với N là số nguyên tố. Điều kiện N nguyên tố sẽ bảo đảm tồn tại nghịch đảo cho mọi phần tử (trừ phần tử 0) đối với phép nhân.

Trường Galoa (Galois Field)

Trong ví dụ trên, khi N là số nguyên tố, ta ký hiệu là số p. Khi đó kết quả phép tính modulo p của tập các số tự nhiên tạo nên trường Galoa modulo p ký hiệu là GF(p). Trường Galoa thỏa tất cả các luật số học (giao hoán, kết hợp, phân phối) và các luật của nhóm Abel cho phép cộng và phép nhân (đóng, bất biến, nghịch đảo).

Trường Galoa GF(qn)

Là tập tất cả các đa thức nguyên có bậc nhỏ hơn n và hệ số nhỏ hơn q. Tất cả các đa thức nguyên sẽ được ánh xạ đến GF(qn) bằng cách rút gọn các hệ số theo modulo q và rút gọn bậc của đa thức theo modulo của một đa thức tối giản có bậc n.Trong lý thuyết mật mã, chúng ta thường xuyên làm việc với trường Galoa GF(2n).

Trường Galoa GF(2n) bao gồm các phần tử là các đa thức nguyên bậc không quá (n-1): a(x) = an-1 xn-1 + an-2 xn-2 +…+ a1x + a0, trong đó các hệ số ai là các số có giá trị là 0 hoặc 1. Ngoài ra, GF(2n) sử dụng một đa thức tối giản d(x) bậc n để rút gọn các đa thức có bậc không nhỏ hơn n.

Các phép tính trên đa thức

Ta sẽ khảo sát một số phép tính modulo trên các đa thức.

  1. Tính “đa thức dư cũng tương tự như tính số dư đối với các số: Số dư đa thức p(x) cho đa thức d(x) (deg p(x) ≥ deg d(x)) là đa thức duy nhất r(x) thoả điều kiện p(x) = q(x) × d(x) + r(x) với điều kiện deg r(x) < deg d(x). Nếu r(x) = 0 ta nói d(x) chia hết p(x), hoặc d(x) là thừa số của p(x). r(x) gọi là đa thức dư. Thông thường người ta chọn d(x) là đa thức tối giản (đa thức nguyên tố), tức là nó chỉ có thừa số là 1 và chính nó.
  1. Phép rút gọn p(x) theo modulo d(x) là tìm đa thức dư r(x) sao cho: p(x) = q(x) × d(x) + r(x). Ta thấy, số hạng bậc cao nhất của q(x) và d(x) nhân với nhau sẽ ra số hạng bậc cao nhất của p(x) từ đó để giảm bậc của đa thức ta sẽ rút gọn số hạng cao nhất trước bằng cách thay nó bởi phần còn lại của đa thức tối giản (đó là một tính chất của toán tử XOR).

Để minh hoạ, ta xét GF(23) = {0, 1, x, x + 1, x2, x2 + 1, x2 + x, x2 + x + 1}, hay là các số 3 bit: {000, 001, 010, 011, 100, 101, 110, 111}. Để rút gọn các đa thức bậc cao, ta sử dụng đa thức tối giản d(x) = x3 + x + 1 hay 1011.

Có thể thấy, x3 có thể được rút gọn bằng cách thay nó bởi x + 1. Ví dụ: Rút gọn p(x) = x4 + x3 + x2 + x hay: 11110.

Ta có: x3 = d(x) + x + 1 = (x + 1) mod d(x) 🡪 x4 = (x2 + x) mod d(x). Do đó: p(x) = x4 + x3 + x2 + x = (x2 + x) + (x + 1) + x2 + x = (x + 1) mod d(x). Tương tự cho chuỗi bit ta cũng có: 11110 = 10000 + 1000 + 110 = 110+ 11 + 110 = 11.

  1. Phép cộng đa thức

Cộng trong GF(qn) là lấy tổng các hệ số tương ứng theo mod q:

Nếu a(x) = an-1xn-1 +…+ a1x + a0 và b(x) = bn-1xn-1 +…+ b1x + b0 thì a(x) ⊕ b(x) = (an-1 ⊕ bn-1) × xn-1 +…+ (a1 ⊕ b1) × x + (a0 ⊕ b0). Ở đây,

phép tính ⊕ là phép cộng hai hệ số, sau đó lấy modulo q.

Trong GF(2n) thì phép cộng hai đa thức chính là phép XOR của hai số n bit. Kết quả của phép tính cộng đa thức trong GF(23) có thể được tham chiếu theo bảng dưới đây:

Lý thuyết số Nhóm, vành, trường
  1. Phép nhân đa thức

Nhân trong GF(qn) là nhân 2 đa thức bình thường sau đó:

  • Rút gọn các hệ số theo mod q
  • Rút gọn đa thức theo mod d(x); ( d(x) là đa thức tối giản bậc n)
Lý thuyết số Nhóm, vành, trường
  1. Biểu diễn đa thức trên GF(2n)

Có thể biểu diễn các đa thức trên GF(2n) như là các chuỗi bit của các

hệ số:

a(x) = an-1 an-2 … a1 a0

Ví dụ: Trong GF(23): x2 + 1 ⬄ 101; x2 + x + 1 ⬄ 111

Phép cộng XOR (⊕)

Ví dụ: (x2+1) ⊕ (x2+x+1) = x ⬄ 101 ⊕ 111 = 010

Phép nhân Dịch chuyển & XOR (với d(x) = x3 + x + 1)

Ví dụ: (x+1) (x2 +1) = x (x2 +1) + 1 (x2 +1) = x3 + x + x2 + 1 = x +1 + x + x2 + 1 = x2

011 101 = dịch trái 1 bit (101) ⊕ dịch trái 0 bit (101) = 1010 ⊕ 101

= 1111 = 1111 + 1011 = 100

Rút gọn modulo Rút gọn từ trái sang phải

Ví dụ: Rút gọn x3 + x2 + x + 1 = (x + 1) + (x2 + x + 1) = x2 1111 = 1111 ⊕ 1011 = 100

Leave a Reply