›
›

Bài giảng Cơ sở Toán học của mã chống nhiễu

pptx 66 trang huongle 3520
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cơ sở Toán học của mã chống nhiễu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptxbai_giang_co_so_toan_hoc_cua_ma_chong_nhieu.pptx

Nội dung text: Bài giảng Cơ sở Toán học của mã chống nhiễu

  1. CƠ SỞ TOÁN HỌC CỦA MÃ CHỐNG NHIỄU
  2. Cơ sở toán học của mã chống nhiễu ◼ Bài này trình bày các cơ sở toán học của mã khối tuyến tính. ◼ Các kiến thức này là rất quan trọng để hiểu được cách xây dựng các loại mã khối tuyến tính. ◼ Các khái niệm được trình bày bao gồm các cấu trúc đại số như nhóm, trường và đặc biệt là các trường GF(2) và GF(2m), đây là các trường có ứng dụng đặc biệt vào trong việc xây dựng các mã khối tuyến tính chống nhiễu. Trang 2
  3. Cơ sở toán học của mã chống nhiễu 11.1 Một số khái niệm cơ bản 11.2 Trường GF(2) và các đa thức trên trường GF(2) 11.3 Trường GF(2m) Trang 3
  4. Một số khái niệm cơ bản ◼ Phép toán đóng ◼ Cho G là một tập hợp, một phép toán hai ngôi f được gọi là đóng trên G nếu f có dạng f : G G → G tức là nếu a, b G thì f(a, b) G. ◼ Chú ý ◼ f(a, b) có một cách viết tương đương là afb và ngược lại f(b, a) còn được viết là bfa. Chẳng hạn nếu f là phép cộng thì thay vì viết +(a, b) chúng ta thường viết là a + b. ◼ Kể từ đây trở về sau khi nói đến một phép toán nếu chúng ta không nói gì thêm thì có nghĩa là phép toán này có tính đóng. Trang 4
  5. Một số khái niệm cơ bản (tt) ◼ Tính kết hợp ◼ Một phép toán hai ngôi f trên G được gọi là có tính kết hợp nếu  a, b, c G thì (afb)fc = af(bfc) ◼ Tính giao hoán ◼ Một phép toán hai ngôi f trên G được gọi là có tính giao hoán nếu  a, b G thì afb = bfa ◼ Ví dụ ◼ Trên tập số thực khác 0, phép cộng và phép nhân có tính kết hợp và giao hoán nhưng phép trừ và phép chia không có tính kết hợp và giao hoán. Trang 5
  6. Nhóm ◼ Tính phân phối ◼ Phép toán f1 được gọi là có tính phân phối đối với phép toán f2 nếu  a, b, c G thì af1(bf2c) = (af1b)f2(af1c) ◼ Chẳng hạn trên tập số thực, phép nhân có tính phân phối đối với phép cộng vì  a, b, c R a (b+c) = (a b)+(a c) ◼ Nhóm ◼ Một tập G , với một phép toán hai ngôi f được gọi là một nhóm nếu thoả 3 điều kiện sau: (1) f có tính kết hợp. Trang 6
  7. Nhóm (tt) (2) G chứa phần tử e, sao cho  a G thì afe = efa = a. e được gọi là phần tử trung hoà (đối với một số phép toán e còn được gọi là phần tử đơn vị) (3) Mọi phần tử đều có phần tử đối xứng, tức là  a G, tồn tại phần tử b G sao cho afb = bfa = e ◼ Chẳng hạn, trên tập R nếu f là phép cộng thì phần tử trung hoà là số 0, còn trên tập số thực khác 0 nếu f là phép nhân thì phần tử trung hoà là 1 và còn được gọi là phần tử đơn vị. ◼ Nhóm giao hoán ◼ Một nhóm mà phép toán f có tính giao hoán thì được gọi là nhóm giao hoán. Trang 7
  8. Nhóm (tt) ◼ Nhóm hữu hạn, nhóm vô hạn ◼ Một nhóm có số phần tử hữu hạn được gọi là nhóm hữu hạn, một nhóm có số phần tử vô hạn được gọi là nhóm vô hạn. ◼ Nhóm con ◼ Cho G là một nhóm. Một tập H con của G được gọi là một nhóm con nếu H đóng với phép toán hai ngôi của G và thoả điều kiện của một nhóm. Trang 8
  9. Phép cộng và nhân modulo ◼ Phép cộng modulo và phép nhân modulo ◼ Cho một số nguyên dương m xác định. Xây dựng một tập số nguyên sau G = {0, 1, , m –1}. Với + là phép cộng thông thường. Định nghĩa phép toán mới  như sau và gọi là phép cộng modulo  a, b G thì a  b = (a + b) mod m ◼ Tương tự với là phép nhân thông thường. Định nghĩa phép toán mới  như sau và gọi là phép nhân modulo  a, b G thì a  b = (a b) mod m Trang 9
  10. Ví dụ ◼ Tập R là một nhóm giao hoán đối với phép cộng và là một nhóm vô hạn. ◼ Tập R – {0} là một nhóm giao hoán đối với phép nhân và là một nhóm vô hạn. ◼ Với m là một số nguyên dương xác định, tập G = {0, 1, , m – 1} với phép cộng modulo là một nhóm giao hoán và là một nhóm hữu hạn. ◼ Hai bảng sau đây trình bày lần lượt trường hợp m = 5 và m = 6. Trang 10
  11. Ví dụ (tt) m = 5 m = 6  0 1 2 3 4  0 1 2 3 4 5 0 0 1 2 3 4 0 0 1 2 3 4 5 1 1 2 3 4 0 1 1 2 3 4 5 0 2 2 3 4 0 1 2 2 3 4 5 0 1 3 3 4 0 1 2 3 3 4 5 0 1 2 4 4 0 1 2 3 4 4 5 0 1 2 3 5 5 0 1 2 3 4 ◼ Tương tự tập G = {1, , m –1} với phép nhân modulo và m nguyên tố là một nhóm giao hoán hữu hạn. Trang 11
  12. Bổ đề ◼ Bổ đề 11.1 ◼ Nếu m là một số nguyên tố thì G = {1, , m – 1} là một nhóm giao hoán với phép nhân modulo . Ngược lại nếu m không nguyên tố thì G không là một nhóm. m = 5 m = 6  1 2 3 4  1 2 3 4 5 1 1 2 3 4 1 1 2 3 4 5 2 2 4 1 3 2 2 4 0 2 4 3 3 1 4 2 3 3 0 3 0 3 4 4 3 2 1 4 4 2 0 4 2 5 5 4 3 2 1 Trang 12
  13. Trường ◼ Trường ◼ Một tập G với hai phép toán đóng hai ngôi bất kỳ, chẳng hạn kí hiệu là + và *, được gọi là một trường nếu thoả 3 điều kiện sau (1) G là nhóm giao hoán đối với phép +. Phần tử trung hoà trong phép + thường được kí hiệu là 0. (2) Tập các phần tử khác 0 là một nhóm đối với phép *. Phần tử trung hoà trong phép * thường được gọi là phần tử đơn vị và kí hiệu là 1. (3) Phép * có tính phân phối đối với phép +. ◼ Chú ý ◼ Phép + và phép * ở trên không nhất thiết là phép cộng và phép nhân thông thường mà chúng có thể là bất kỳ phép nào. Chúng ta kí hiệu như vậy để dễ trình bày. Trang 13
  14. Trường (tt) ◼ Các phần tử của một trường không nhất thiết là các số nguyên hay thực mà có thể là bất kỳ cái gì, chẳng hạn có thể là các số phức, vectơ, ma trận hay đa thức ◼ Từ định nghĩa của trường chúng ta suy ra một trường bao gồm tối thiểu hai phần tử: phần tử trung hoà của phép + (kí hiệu là 0) và phần tử trung hoà của phép * (kí hiệu là 1). Các phần tử 0 và 1 không nhất thiết là số 0 và số 1 theo nghĩa thông thường mà có thể là bất kỳ cái gì chẳng hạn là ma trận 0 và ma trận đơn vị, ◼ Trường giao hoán ◼ Một trường mà phép * có tính giao hoán thì được gọi là trường giao hoán. Trang 14
  15. Trường (tt) ◼ Chẳng hạn trong ví dụ ở slide 201 với m = 5 chúng ta thấy G là một trường giao hoán. ◼ Tổng quát chúng ta có bổ đề sau và để dành việc chứng minh cho các bạn sinh viên. ◼ Bổ đề 11.2 ◼ Cho p là một số nguyên tố bất kỳ, G = {0, 1, , p – 1} thì G là một trường giao hoán đối với phép cộng modulo  và phép nhân modulo . ◼ Sau đây là một số tính chất của trường ◼ Tính chất 1 ◼ Mọi phần tử a của trường đều thoả a * 0 = 0. Trang 15
  16. Trường Galois ◼ Tính chất 2 ◼ Nếu a, b là hai phần tử khác 0 của trường thì a * b 0. ◼ Tính chất 3 ◼ Nếu a 0 và a * b = a * c thì b = c. Hay nói cách khác nếu a 0 và b c thì a * b a * c. ◼ Bậc của một trường, trường hữu hạn, trường vô hạn. ◼ Số phần tử của một trường được gọi là bậc của một trường. Một trường có số phần tử hữu hạn được gọi là trường hữu hạn, một trường có số phần tử vô hạn được gọi là trường vô hạn. ◼ Trường GF(q) ◼ Một trường có số phần tử hữu hạn được gọi là trường Galois. Nếu bậc của trường Galois là q thì trường được kí hiệu là GF(q). Trang 16
  17. Trường Galois ◼ Đối với các trường hữu hạn tức là trường Galois chúng ta có định lý sau. ◼ Định lý 11.1 m ◼ Một trường hữu hạn thì số phần tử của nó phải có dạng p trong đó p là một số nguyên tố còn m là một số nguyên dương. Hay nói cách khác các trường Galois đều có dạng GF(pm) trong đó p là một số nguyên tố còn m là một số nguyên dương. ◼ Đối với các trường GF(p) với p nguyên tố thì đó chính là tập {0, 1, 2, , p – 1} với hai phép toán cộng modulo  và nhân modulo  như đã biết. m ◼ Đối với các trường GF(p ), vì tính phức tạp của chúng, chúng ta sẽ giới thiệu sau. Chú ý lúc này các phần tử của trường GF(pm) không đơn thuần là các số mà sẽ có dạng khá đặc biệt. Trang 17
  18. Trường Galois (tt) ◼ Kí hiệu các phần tử đối xứng ◼ Phần tử đối xứng của a trong phép + được kí hiệu là –a, phần tử đối xứng của a trong phép * được kí hiệu là a–1. ◼ Phép – và phép / ◼ Đối với một trường giao hoán, từ hai phép + và phép * chúng ta định nghĩa thêm hai phép – và phép / như sau (không nhất thiết là phép trừ và phép chia bình thường) a – b = a + (–b) a / b = a * b–1 trong đó –b là phần tử đối xứng của b qua phép +, còn b–1 là phần tử đối xứng của b qua phép *. ◼ Vậy một trường giao hoán G có bốn phép toán +, –, *, /. Phép + và – đóng trên G, phép * và / đóng trên G – {0}. Trang 18
  19. Trị riêng của một trường ◼ Xét một trường GF(q). Xét các dãy tổng của các phần tử đơn vị k 1 = 1+ 1+  + 1 (k lần, với k = 1, 2, 3, ) i=1 ◼ Vì trường đóng với phép cộng nên kết quả của những tổng này cũng là các phần tử của trường. Vì k có thể nhận vô hạn giá trị mà trường chỉ có q phần tử nên tồn tại hai giá trị k1 và k2 khác nhau (giả sử k1 > k2 ) sao cho k1 k2 1 = 1 ◼ Từ đây suy ra i=1 i=1 k1 −k2 1 = 0 i=1 Trang 19
  20. Trị riêng của một trường ◼ Trị riêng của một trường kí hiệu là số nguyên dương nhỏ nhất  sao cho  1 = 0 i =1 ◼ Dễ thấy đối với các trường GF(p) = {0, 1, 2, , p – 1} với p là một số nguyên tố thì trị riêng  = p. Tổng quát chúng ta có định lý sau. ◼ Định lý 11.2 ◼ Trị riêng  của một trường GF(q) là một số nguyên tố. ◼ Chứng minh ◼ Giả sử  không nguyên tố  = k l (k, l nguyên > 1). Từ qui tắc phân phối của phép nhân đối với phép cộng suy ra Trang 20
  21. Trị riêng của một trường (tt) k l k l  1 1 = 1 = 1 = 0 i=1 i=1 i=1 i=1 Suy ra k l 1 = 0 1 = 0  hoặc  i =1 i =1 Mà k, l k2 ) sao cho ak1 = ak2 ak1 − k2 = 1 Trang 21
  22. Chu kỳ của một phần tử ◼ Chu kỳ của một phần tử a của một trường GF(q) là số nguyên dương nhỏ nhất n sao cho an = 1. ◼ Ví dụ ◼ Xét trường GF(7) = {0, 1, 2, 3, 4, 5, 6} với hai phép  và . Trị riêng của trường này là 7. Còn chu kỳ của các phần tử khác 0 của trường được trình bày trong bảng sau Phần tử 1 2 3 4 5 6 Chu kỳ 1 3 6 3 6 2 ◼ Từ định nghĩa trên chúng ta thấy dãy các luỹ thừa của a a1, a2, , ak, , an = 1, an+1 = a, sẽ lặp lại sau n phần tử. Trang 22
  23. Nhóm tuần hoàn ◼ Bổ đề 11.3 1 2 k n ◼ Dãy a , a , , a , , a = 1 tạo nên một nhóm con đóng với phép nhân trên trường GF(q). ◼ Nhóm tuần hoàn ◼ Một nhóm (không chứa phần tử 0) với phép nhân * được gọi là tuần hoàn nếu tồn tại một phần tử trong nhóm mà các luỹ thừa của nó tạo nên mọi phần tử trong nhóm. ◼ Từ định nghĩa này suy ra một nhóm hữu hạn được gọi là tuần hoàn nếu tồn tại một phần tử trong nhóm có chu kỳ đúng bằng số phần tử của nhóm. ◼ Định lý 11.3 ◼ Nếu a là một phần tử khác 0 của một trường GF(q) thì aq–1 = 1 Trang 23
  24. Nhóm tuần hoàn (tt) ◼ Chứng minh ◼ Gọi b1, b2, , bq-1 là q – 1 phần tử khác nhau và khác 0 của trường. Theo tính chất 3 và tính chất 2 của trường chúng ta có a*b1, a*b2, , a*bq-1 cũng là q – 1 phần tử khác nhau và khác 0 của trường. Vì vậy chúng ta có a*b1*a*b2* *a*bq-1 = b1*b2* *bq-1 q–1 ◼ Từ đây suy ra a = 1. Hoàn tất chứng minh. ◼ Định lý 11.4 ◼ Chu kỳ của một phần tử bất kỳ khác 0 của một trường GF(q) là ước số của q – 1. Trang 24
  25. Phần tử cơ sở ◼ Chứng minh ◼ Gọi n là chu kỳ của phần tử a khác 0 của trường GF(q). Giả sử q – 1 không chia hết cho n. Do đó q – 1 = kn + r, trong đó r là số dư của phép chia q – 1 cho n, 0 < r < n. Chúng ta có q-1 kn+r n k r a = a = (a ) *a Do aq-1 = 1 và an = 1 suy ra ar = 1. Mà 0 < r < n điều này mâu thuẫn với định nghĩa chu kỳ của a. Vậy q – 1 chia hết cho n. ◼ Phần tử cơ sở ◼ Một phần tử a khác 0 của một trường GF(q) được gọi là phần tử cơ sở nếu chu kỳ của a bằng q – 1. ◼ Từ định nghĩa này nếu a là một phần tử cơ sở thì các luỹ thừa của a gồm a0 = 1, a1 = a, a2, , aq – 2 hình thành nên q – 1 phần tử khác 0 của trường. Trang 25
  26. Ví dụ ◼ Xét trường GF(7) như trong ví dụ ở slide 211. Chu kỳ của các phần tử khác 0 của trường đều là ước số của 6. Đặc biệt các phần tử 3 và 5 có chu kỳ bằng 6 nên chúng là các phần tử cơ sở của trường GF(7). 31 = 3 32 = 2 33 = 6 34 = 4 35 = 5 36 = 1 51 = 5 52 = 4 53 = 6 54 = 2 55 = 3 56 = 1 m ◼ Trong các trường Galois thì trường GF(2) và trường GF(2 ) là những trường có nhiều ứng dụng đặc biệt trong lý thuyết mã, nên chúng ta sẽ chỉ trình bày hai trường này. Trang 26
  27. Trường GF(2) ◼ Trường GF(2) ◼ Trường GF(2) bao gồm hai phần tử {0, 1} với hai phép cộng + và nhân * như sau + 0 1 * 0 1 0 0 1 0 0 0 1 1 0 1 0 1 ◼ Phần tử đối xứng của 0 và 1 qua phép cộng cũng chính là 0 và 1. Phần tử đối xứng của 1 qua phép nhân cũng chính là 1. ◼ Trong trường GF(2) thì phép trừ giống với phép cộng, phép chia cho một số khác 0 cũng giống với phép nhân. Trang 27
  28. Các đa thức trên trường GF(2) ◼ Đa thức trên trường GF(2) ◼ Một đa thức trên trường GF(2), chẳng hạn kí hiệu là f(x), là đa thức có dạng 2 n f(x) = a0 + a1x + a2x + + anx trong đó các hệ số ai GF(2). ◼ Bậc của đa thức ◼ Là bậc lớn nhất của đa thức. ◼ Ví dụ 3 2 5 ◼ Đa thức f(x) = 1 + x + x có bậc 3 đa thức g(x) = x + x + x có bậc 5. Trang 28
  29. Các đa thức trên trường GF(2) (tt) ◼ Phép cộng đa thức và nhân đa thức 2 n 2 ◼ Với f(x) = a0 + a1x + a2x + + anx , g(x) = b0 + b1x + b2x + n + bnx với các hệ số ai và bj thuộc trường GF(2) chúng ta định nghĩa các phép cộng đa thức và nhân đa thức như sau n i f(x) + g(x) =  (ai + bi )x i = 0 n i + j f(x) * g(x) =  (ai *b j )x i, j = 0 trong đó ai + bi và ai * bj được thực hiện trên trường GF(2). Trang 29
  30. Các đa thức trên trường GF(2) (tt) ◼ Ví dụ 3 2 ◼ Cho f(x) = 1 + x + x , g(x) = x + x thì f(x) + g(x) = (1 + x + x3) + (x + x2) = 1 + x2 + x3 f(x) * g(x) = (1 + x + x3) * (x + x2) = x + x3 + x4 + x5 ◼ Nếu g(x) có bậc khác 0 thì chúng ta có thể chia f(x) cho g(x) và có thể viết như sau f(x) = q(x) * g(x) + r(x) trong đó q(x) là đa thức thương còn r(x) là đa thức dư có bậc nhỏ hơn đa thức chia g(x). ◼ Ví dụ 4 5 6 3 ◼ f(x) = 1 + x + x + x + x chia cho g(x) = 1 + x + x Trang 30
  31. Các đa thức trên trường GF(2) (tt) 4 5 6 2 3 3 2 ◼ 1 + x + x + x + x = (x + x ) * (1 + x + x ) + (1 + x + x ) ◼ Để phân tích một đa thức ra thành các thừa số trong đại số Euclid chúng ta có ◼ Nếu f(a) = 0 thì f(x) chia hết cho (x - a). ◼ Điều này cũng đúng trên trường GF(2). ◼ Ví dụ 3 5 ◼ f(x) = 1 + x + x + x có f(1) = 0, nên f(x) chia hết cho (x - 1) mà trong trường GF(2), phép trừ cũng chính là phép cộng tức là f(x) chia hết cho (x + 1). 1 + x + x3 + x5 = (1 + x)(1 + x3 + x4) Trang 31
  32. Đa thức tối giản ◼ Một đa thức trên GF(2) được gọi là tối giản nếu nó không phân tích được thành tích của hai đa thức có bậc nhỏ hơn. 1, 2, 3, 4 5 6 x 1 + x2 + x5 1 + x + x6 1 + x 1 + x3 + x5 1 + x3 + x6 1 + x + x2 1 + x + x2 + x3 + x5 1 + x + x2 + x4 + x6 1 + x + x3 1 + x + x2 + x4 + x5 1 + x + x3 + x4 + x6 1 + x2 + x3 1 + x + x3 + x4 + x5 1 + x5 + x6 1 + x + x4 1 + x2 + x3 + x4 + x5 1 + x + x2 + x5 + x6 1 + x3 + x4 1 + x2 + x3 + x5 + x6 1 + x + x2 + x3 + x4 1 + x + x4 + x5 + x6 Trang 32 1 + x2 + x4 + x5 + x6
  33. Bổ đề ◼ Cho f(x) là một đa thức trên trường GF(2), thì n n f (x)2 = f (x2 ) ◼ Chứng minh n ◼ Đặt f(x) = a0 + a1x + + anx . 2 n 2 [f(x)] = (a0 + a1x + + anx ) 2 n n = a0 + a0*(a1x + + anx ) + a0*(a1x + + anx ) + n 2 (a1x + + anx ) 2 n 2 = a0 + (a1x + + anx ) 2 2 n 2 = a0 + (a1x) + + (anx ) 2 2 = f(x ) (vì trong GF(2) ai = ai ) ◼ Điều này cũng giúp chúng ta suy ra điều phải chứng minh. Trang 33
  34. Trường GF(2m) m ◼ Trước hết chúng ta kí hiệu trường GF(2 ) như sau m GF(2 ) = {0, 1, a , a , , a m } 1 2 2 − 2 trong đó 0 và 1 GF(2). Trường GF(2) là một trường con của GF(2m) và được gọi là trường cơ sở của GF(2m). ◼ Chú ý m ◼ Nếu a là một phần tử GF(2 ), f(x) là một đa thức trên trường GF(2), thì f(a) cũng là một phần tử của GF(2m). ◼ Có vô hạn đa thức f(x) trên trường GF(2) mà chỉ có hữu hạn (2m) phần tử GF(2m), nên  a 0 của GF(2m) tồn tại hai đa thức f1(x) và f2(x) khác nhau sao cho f1(a) = f2(a). Từ đây nếu đặt f(x) = f1(x) – f2(x) (chú ý trong trường GF(2) thì phép – giống với phép cộng +) thì f(a) = 0. Trang 34
  35. Đa thức tối thiểu ◼ Đa thức tối thiểu (minimal polinomial) m ◼ Cho a là một phần tử khác 0 của trường GF(2 ). Đa thức tối thiểu của a là đa thức f(x) khác 0 trên trường GF(2) và có bậc nhỏ nhất sao cho f(a) = 0. ◼ Một lần nữa ta phải chú ý rằng khi chúng ta viết f( ) = 0 hoặc f( ) = 1 thì các kí hiệu 0 và 1 không nhất thiết là các số 0 và 1, mà sẽ được hiểu tuỳ theo ngữ cảnh. ◼ Chẳng hạn nếu phần tử là một ma trận thì 0 chính là ma trận 0 còn 1 chính là ma trận đơn vị. Trang 35
  36. Đa thức tối thiểu (tt) 0 1 0 0 ◼ Ví dụ 0 0 1 0 ◼ Chẳng hạn nếu a là ma trận 4 4 bên T = 4 4 0 0 0 1 1 1 0 0 trong đó các phép cộng và nhân trên ma trận vẫn thực hiện như bình thường với chú ý rằng các phép cộng và nhân các phần tử của ma trận được thực hiện trên trường GF(2). ◼ Chúng ta có thể kiểm tra rằng 1 + T + T4 = 0 với chú ý rằng 1 là ma trận đơn vị, còn 0 là ma trận 0. 4 ◼ Và f(x) = 1 + x + x là đa thức tối thiểu của a Trang 36
  37. Định lý ◼ Hơn nữa chúng ta cũng có T15 = 1 và chúng ta có thể kiểm tra rằng 15 chính là chu kỳ của a. ◼ Định lý 11.5 m ◼ Cho a là một phần tử khác 0 của trường GF(2 ) có bậc của đa thức tối thiểu của a là k. Gọi Z là tập tất cả các phần tử có dạng k-1 b0 + b1a + + bk-1a m trong đó bi GF(2). Thì Z là một tập con của GF(2 ) và hình thành nên một trường có 2k phần tử. Trang 37
  38. Chứng minh ◼ Đầu tiên chúng ta chứng minh các phần tử được hình thành từ b0 + b1a + + bk-1ak-1 là khác nhau bằng cách chứng minh các phần tử 1, a, a2, , ak-1 là độc lập tuyến tính. Thật vậy nếu k −1 k −1 i i bia =  cia i=0 i=0 thì k −1 i p(a) =  (bi − ci )a = 0 i=0 Vậy chúng ta có đa thức p(x) có bậc nhỏ hơn k thoã p(a) = 0. Mà bậc của đa thức tối thiểu của a bằng k. Vậy p(x) = 0, suy ra bi = ci  i = 0, 1, , k – 1. Trang 38
  39. Chứng minh (tt) ◼ Thứ hai, rõ ràng Z là một nhóm giao hoán đối với phép +. Thật vậy nếu k −1 k −1 k −1 k −1 i i i i bia Z,  cia Z  (bi + ci )a =  (ci + bi )a Z i=0 i=0 i=0 i=0 Để chứng minh tập Z0 = Z – {0} là một nhóm đối với phép nhân * chúng ta chứng minh nếu k −1 k −1 k −1 k −1 i i i i bia Z0 ,  cia Z0 bia *  cia Z0 i=0 i=0 i=0 i=0 k i Gọi f ( x ) =  d i x là đa thức tối thiểu của a, trong đó hệ số i=0 cao nhất dk = 1. Trang 39
  40. Chứng minh (tt) k −1 Từ đây suy ra k i x =  di x i=0 Do đó mọi an với n k đều có thể biểu diễn thông qua một đa k −1 k −1 thức g(a) nào đó có bậc k – 1. Vì vậy i i bia *  cia k −1 k −1 i=0 i=0 cũng vậy. Suy ra i i bia *  cia Z i=0 i=0 Và rõ ràng nếu k −1 k −1 k −1 k −1 i c ai 0 b ai * c ai 0  bia 0,  i  i  i i=0 i=0 i=0 i=0 Tính chất này được kế thừa từ trường GF(2m). Trang 40
  41. Hệ quả ◼ Cuối cùng tính phân phối của phép nhân * đối với phép cộng + chúng ta cũng kế thừa từ trường GF(2m). Chứng minh hoàn tất. ◼ Hệ quả 11.1 m ◼ Nếu đa thức tối thiểu của phần tử a GF(2 ) có bậc bằng m thì trường Z trùng với trường GF(2m) và mỗi phần tử của trường có thể được biểu diễn như một vectơ m thành phần (b0b1 bm-1) ◼ Định lý 11.6 ◼ Gọi f(x) là đa thức tối thiểu của phần tử a 0 của trường GF(2m) thì f(x) là đa thức tối giản trên trường GF(2). Trang 41
  42. Chứng minh ◼ Giả sử f(x) = g(x) * h(x) trong đó g(x) và h(x) có bậc lớn hơn 0 và nhỏ hơn bậc của f(x). Chúng ta có f(a) = g(a) * h(a) = 0, suy ra g(a) = 0 hoặc h(a) = 0. Điều này mâu thuẫn với định nghĩa về đa thức tối thiểu của a. ◼ Bổ để 11.5 ◼ Cho f(x) là đa thức tối thiểu của phần tử a 0 của trường GF(2m) và p(x) là đa thức bất kỳ trên trường GF(2) sao cho p(a) = 0. Thì p(x) chia hết cho f(x). ◼ Chứng minh ◼ Chia p(x) cho f(x) chúng ta được p(x) = g(x) * f(x) + r(x) trong đó bậc của r(x) nhỏ hơn bậc của f(x). Thay x = a r(a) = 0, nên từ định nghĩa của đa thức tối thiểu r(x) = 0 p(x) chia hết cho f(x). Trang 42
  43. Định lý ◼ Định lý 11.7 ◼ Cho f(x) là đa thức tối thiểu của phần tử a 0 của trường GF(2m) và p(x) là đa thức tối giản trên trường GF(2) sao cho p(a) = 0. Thì f(x) = p(x). ◼ Chứng minh ◼ Theo Bổ đề 11.5 trên chúng ta có p(x) chia hết cho f(x) tức là chúng ta có thể viết p(x) = g(x) * f(x) Do p(x) là đa thức tối giản nên f(x) = 1 hoặc f(x) = p(x). Tuy nhiên f(x) không thể bằng 1 nên suy ra f(x) = p(x). ◼ Hệ quả 11.2 m m ◼ 2 – 1 phần tử khác 0 của trường GF(2 ) đều là nghiệm của phương trình m x2 −1 +1 = 0 Trang 43
  44. Hệ quả ◼ Hệ quả 11.3 2m −1 ◼ x + 1 chia hết cho các đa thức tối thiểu của các phần tử khác 0 của trường GF(2m). ◼ Chúng ta sẽ dẫn ra một hệ quả mạnh hơn như sau. Trước hết chúng ta phân tích thành tích của các đa thức tối giản trên trường GF(2) = p1(x) * p2(x) * * pl(x) Vì có các nghiệm là các phần tử của trường GF(2m) m nên các phần tử của trường GF(2 ) sẽ là nghiệm của một pi(x) nào đó và ngược lại một pi(x) bất kỳ sẽ có các nghiệm là các phần tử của trường GF(2m). Hơn nữa nếu pi(x) có bậc t thì sẽ có t nghiệm trong trường GF(2m). Trang 44
  45. Hệ quả ◼ Hệ quả 11.4 2m −1 ◼ Trong việc triển khai x + 1 thành tích các đa thức tối giản, thì mỗi đa thức tối giản sẽ là đa thức tối thiểu của một phần tử khác 0 nào đó của trường GF(2m). ◼ Định lý 11.8 m ◼ Cho a là một phần tử khác 0 của trường GF(2 ) và f(x) là một đa thức trên trường GF(2). Nếu f(a) = 0 thì 2l f (a ) = 0  l = 0, 1, 2, ◼ Hệ quả 11.5 ◼ Nếu f(x) là đa thức tối thiểu của phần tử a 0 của trường GF(2m) thì f(x) cũng là đa thức tối thiểu của các phần tử l a2 với l = 0, 1, 2, của trường GF(2m). Trang 45
  46. Hệ quả (tt) 2l ◼ Hay nói cách khác các phần tử a với l = 0, 1, 2, là các nghiệm của đa thức tối thiểu f(x) của phần tử a. ◼ Hơn nữa chúng ta sẽ chứng minh rằng ngoài chúng ra f(x) không còn nghiệm nào khác thuộc trường GF(2m). ◼ Vì vậy nếu có bao nhiêu phần tử khác nhau thì f(x) có bậc bấy nhiêu. ◼ Để làm rõ điều này gọi k là số nguyên dương nhỏ nhất sao cho k a2 = a Số k chắc chắn tồn tại vì chúng ta đã có m m a2 −1 = 1 hay a2 = a Và số k biểu diễn chu kỳ của dãy với l = 0, 1, 2, Trang 46
  47. Bổ đề ◼ Bổ dề 11.6 m ◼ Cho a là một phần tử khác 0 của trường GF(2 ) và k là số nguyên dương nhỏ nhất sao cho k a2 = a thì k là một ước số của m. l a2 ◼ Chứng minh ◼ Chia m cho k, m = n k + r, trong đó r là số dư và r < k 2k k k k 2k a2 = a a2 = a2 = a hay a2 = a nk Tiếp tục theo kiểu này chúng ta có a 2 = a . Mặt khác chúng ta có 2r m n k +r n k r n k r a = a2 = a2 = a2 2 = a2 = (a)2 Trang 47
  48. Bổ đề (tt) Do định nghĩa của k r = 0. Hoàn tất chứng minh. ◼ Phần tử liên hợp m ◼ Cho a là một phần tử khác 0 của trường GF(2 ) và k là số nguyên dương nhỏ nhất sao cho k l a2 = a thì các phần tử a 2 với l = 0, 1, 2, , k - 1 được gọi là các phần tử liên hợp của a và k được gọi là số phần tử liên hợp của a. ◼ Từ định nghĩa chúng ta thấy tập các phần tử liên hợp của a là tập các phần tử khác nhau được sinh ra bởi với l = 0, 1, 2, ◼ Bổ dề 11.7 ◼ Nếu a1 và a2 là các phần tử liên hợp bất kỳ của a thì a1 là phần tử liên hợp của a2 và ngược lại a2 là phần tử liên hợp của a1. Trang 48
  49. Bổ đề (tt) ◼ Thật vậy giả sử (với k là số phần tử liên hợp của a) l1 l2 a = a2 ,a = a2 ,0 l l k Thì 1 2 1 2 2l2 −l1 2l1 2l2 −l1 2l1 2l2 −l1 2l2 a1 = (a ) = a = a = a2 và 2k +l1 −l2 2l2 2k +l1 −l2 2l2 2k +l1 −l2 a2 = (a ) = a 2k +l1 2k 2l1 2l1 = a = (a ) = a = a1 Hoàn tất chứng minh. ◼ Chú ý bổ đề này nói lên rằng các phần tử liên hợp của a là liên hợp với nhau. Trang 49
  50. Bổ đề (tt) 2l ◼ Vì các phần tử a với l = 0, 1, 2, , k - 1 là các nghiệm của đa thức tối thiểu f(x) của a, nên ta sẽ chứng minh f(x) có dạng k −1 k −1 i f (x) = (x + a) *(x + a2 ) **(x + a2 ) =  (x + a2 ) i=0 ◼ Để chứng minh điều này chúng ta sẽ chứng minh k −1 i p(x) =  (x + a2 ) i=0 là một đa thức tối giản và do p(a) = 0 nên theo Định lý 11.7 chúng ta suy ra f(x) = p(x). Trang 50
  51. Bổ đề (tt) ◼ Bổ dề 11.7 m ◼ Cho a là một phần tử khác 0 của trường GF(2 ) và k là số nguyên dương nhỏ nhất sao cho k a2 = a thì k −1 i p(x) =  (x + a2 ) i=0 là một đa thức tối giản trên trường GF(2). ◼ Chứng minh 2 k −1 i k −1 i p(x)2 =  (x + a2 ) =  (x + a2 )2 i=0 i=0 Trang 51
  52. Chứng minh (tt) i i i i i+1 (x + a2 )2 = x2 + (a2 + a2 )x + (a2 )2 = x2 + a2 k −1 i+1 k i p(x)2 =  (x2 + a2 ) =  (x2 + a2 ) i=0 i=1 k −1 i k =  (x2 + a2 )(x2 + a2 ) i=1 k −1 i k −1 i =  (x2 + a2 )(x2 + a) =  (x2 + a2 ) i=1 i=0 = p(x2 ) Trang 52
  53. Chứng minh (tt) Mặt khác p(x) là một đa thức của x và có thể biểu diễn k p(x) = b0 + b1x + + bkx trong đó các bi với i = 0, 1, 2, , k là các đa thức trên trường m GF(2) của a. Vì vậy các bi là các phần tử của trường GF(2 ). 2 k 2 p(x) = (b0 + b1x + bk x ) k k k k 2 2i i+ j 2 2i = bi x + (1+1)  bib jx = bi x i=0 i=0 j =0 i=0 i j Do [p(x)]2 = p(x2) suy ra 2 bi = bi  i = 0, 1, 2, , k Điều này chỉ đúng nếu các bi bằng phần tử 0 hoặc phần tử 1 tức là các bi GF(2) hay p(x) là một đa thức trên trường GF(2). Trang 53
  54. Chứng minh (tt) Nếu p(x) không tối giản tức p(x) có thể phân tích thành p(x) = q(x) * h(x) trong đó bậc của q(x) và h(x) nhỏ hơn bậc của p(x) là k. Nhưng do p(a) = 0 q(a) = 0 hoặc h(a) = 0. l Giả sử q(a) = 0, theo Định lý 12.8 q(x) có các nghiệm là a2 với l = 0, 1, 2, , k – 1, q(x) có bậc tối thiểu là k, mẫu thuẫn. Từ đây suy ra điều phải chứng minh. ◼ Định lý 11.9 m ◼ Cho a là một phần tử khác 0 của trường GF(2 ) và k là số nguyên dương nhỏ nhất sao cho k a2 = a k −1 i thì đa thức tối thiểu của a là f ( x ) =  ( x + a 2 ) và có bậc = k. i=0 Trang 54
  55. Hệ quả ◼ Hệ quả 11.6 ◼ Bậc của một đa thức tối thiểu của một phần tử a khác 0 của trường GF(2m) là một ước số của m. ◼ Định lý 11.10 2l m a ◼ Cho a là một phần tử khác 0 của trường GF(2 ) có chu kỳ bằng n thì các phần tử liên hợp của a cũng có chu kỳ bằng n. ◼ Chứng minh ◼ Gọi k là số thành phần liên hợp của a.  i = 0, 1, , k n i i i a2 = a2 n = (an )2 = 1 ◼ Chúng ta chứng minh rằng không  số nguyên dương l < n l i a2 = 1 Trang 55
  56. Chứng minh i Thật vậy giả sử tồn tại, suy ra a2 l = 1 Chia 2i l cho n 2i l = h n + r trong đó 0 r < n, i 1 = a2 l = ah n+ r = (an )h ar = ar Từ định nghĩa khái niệm chu kỳ, r = 0. Từ Định lý 11.4 n là một ước số của 2m – 1, n lẽ. Kết hợp với 2i l = h n n là một ước số của l, n l vô lý. ◼ Định lý 11.11 ◼  m ≥ 1 đều tồn tại một đa thức tối giản bậc m trên trường GF(2). Trang 56
  57. Định lý ◼ Định lý 11.12 ◼ Với một đa thức tối giản p(x) bất kỳ có bậc m, m p(x) = b0 + b1x + + bmx trong đó bm = 1, chúng ta luôn xây dựng được một trường GF(2m) trong đó p(x) là đa thức tối thiểu của một phần tử của trường. 0 1 0 0  0 0 Để xây dựng trường 0 0 1 0  0 0 GF(2m) chúng ta cho 0 0 0 1  0 0 phần tử a là một ma Tm m =        trân m m như bên 0 0 0 0  0 1 b0 b1 b2 b3  bm− 2 bm−1 Trang 57
  58. Định lý (tt) ◼ Trên ma trận định nghĩa phép cộng và nhân ma trận như bình thường, với chú ý rằng việc cộng hoặc nhân hai phần tử trong 2 ô của hai ma trận được thực hiện như trên trường GF(2). ◼ Chúng ta công nhận rằng ma trận này có đa thức tối thiểu là p(x). Từ đây chúng ta có thể dẫn ra được các phần tử còn lại của trường GF(2m) nhờ Định lý 11.5. ◼ Chú ý, phần tử 0 chính là ma trận 0 và phần tử 1 chính là ma trận đơn vị. ◼ Định lý 11.13 ◼  m ≥ 2, các đa thức tối giản bậc m trên trường GF(2) đều là ước số của m x2 −1 + 1 ◼ Chúng ta có thể quay trở về bảng liệt kê các đa thức tối giản để kiểm tra rằng các đa thức tối giản bậc 3 là ước số của x7 – 1, các đa thức tối giản bậc 4 là ước số của x15 – 1, Trang 58
  59. Định lý (tt) ◼ Đa thức căn bản ◼ Một đa thức căn bản là một đa thức tối giản, đồng thời không tồn tại số nguyên dương n < 2m – 1 sao cho xn + 1 chia hết cho nó. n ◼ Ví dụ, không tồn tại số nguyên dương n < 15 sao cho x + 1 chia hết cho 1 + x + x4 nên 1 + x + x4 là đa thức căn bản. 2 3 4 ◼ Còn đa thức 1 + x + x + x + x là tối giản nhưng không căn bản vì x5 + 1 chia hết cho nó. 1, 2, 3 4, 5 6, 7, 8 1 + x 1 + x + x4 1 + x + x6 1 + x + x2 1 + x3 + x4 1 + x3 + x7 1 + x + x3 1 + x2 + x5 1 + x2 + x3 + x4 + x8 1 + x2 + x3 1 + x3 + x5 Trang 59
  60. Định lý (tt) ◼ Định lý 11.14 m ◼ Cho a là một phần tử khác 0 của trường GF(2 ) có đa thức tối thiểu là f(x). Nếu f(x) là một đa thức căn bản trên trường GF(2) m và có bậc bằng m thì a có chu kỳ là 2 – 1 và a là một phần tử l cơ sở của GF(2m). a2 ◼ Chứng minh n ◼ Gọi n là chu kỳ của a. Đặt p(x) = x + 1, thì p(a) = 0. Bổ đề 11.5 p(x) chia hết cho f(x). Kết hợp điều này với định nghĩa của khái niệm đa thức căn bản, n = 2m – 1. m ◼ Định lý này gợi ý cho chúng ta cách xây dựng trường GF(2 ) dựa trên một phần tử cơ sở có đa thức tối thiểu là một đa thức căn bản bậc m. Trang 60
  61. Tóm tắt ◼ Tóm tắt m m 2 −1 ◼ a là một phần tử của trường GF(2 ) thì a = 1 m ◼ Chu kỳ của một phần tử là một ước số của 2 – 1. m ◼ Các đa thức tối thiểu của trường GF(2 ) là các đa thức tối giản và là ước số của m x2 −1 + 1 Hơn nữa bậc của chúng là ước của m. ◼ Số phần tử liên hợp khác nhau của a, kể cả a, là ước số của m. Các phần tử liên hợp của nhau có cùng đa thức tối thiểu, hơn nữa chúng là các nghiệm của đa thức tối thiểu này và bậc của đa thức tối thiểu này bằng số các phần tử liên hợp khác nhau. Các phần tử liên hợp thì có cùng chu kỳ. 2k −1 ◼ Các đa thức tối giản bậc k là ước của x + 1 Trang 61
  62. Tóm tắt (tt) ◼ Một phần tử a có đa thức tối thiểu bậc m thì các tổ hợp tuyến tính (với bi GF(2)) k - 1 b01 + b1a + + bk - 1a sẽ sinh ra toàn bộ các phần tử của trường GF(2m) ◼ Một phần tử a có đa thức tối thiểu bậc m và cũng là đa thức căn bản thì các lũy thừa của nó sẽ sinh ra toàn bộ các phần tử của trường GF(2m). Trang 62
  63. Ví dụ m ◼ Xây dựng trường GF(2 ) với m = 4. ◼ Chúng ta kí hiệu 0 là ma trận 0, kí hiệu 1 là ma trận đơn vị (có kích thước là 4 4). Lấy phần tử a là ma trận sau 0 1 0 0 0 0 1 0 T = 4 4 0 0 0 1 1 1 0 0 Chúng ta có đa thức tối thiểu của a là f(x) = 1 + x + x4 ◼ Đây là một đa thức căn bản bậc 4. Vì vậy theo Định lý 11.14, 15 phần tử của GF(24) không tính phần tử 0 sẽ có dạng ai, i = 0, 1, , 14 với chú ý a0 = 1. 2 3 ◼ Còn theo Định lý 12.12 chúng sẽ có dạng b0 + b1a + b2a + b3a trong đó các bi = 0 hoặc 1. Trang 63
  64. Ví dụ (tt) 4 ◼ Vậy có hai cách để xây dựng trường GF(2 ) như trên. ◼ Các bảng sau đây biểu diễn các phần tử khác 0 và khác 1 của trường GF(24) theo các dạng: lũy thừa của a (ai), đa thức của a, vectơ, dạng ma trận. a a2 a3 a4 a5 a a2 a3 1 + a a + a2 0100 0010 0001 1100 0110 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0 1 0 Trang 64
  65. Ví dụ (tt) a6 a7 a8 a9 a10 a2 + a3 1 + a + a3 1 + a2 a + a3 1 + a + a2 0011 1101 1010 0101 1110 0 0 1 1 1 1 0 1 1 1 1 0 1 0 1 0 0 1 0 1 0 1 1 1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 Trang 65
  66. Ví dụ (tt) a11 a12 a13 a14 a + a2 + a3 1 + a + a2 + a3 1 + a2 + a3 1 + a3 0111 1111 1011 1001 0 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 ◼ Chu kỳ, đa thức tối thiểu của các phần tử liên hợp 0 1 a, a2, a4, a8 a3, a6, a12, a9 a5, a10 a7, a14, a13, a11 15 5 3 15 x 1 + x 1 + x + x4 1 + x + x2 + x3 + x4 1 + x + x2 1 + x3 + x4 Trang 66