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

Ơ Ở

Ọ

Ủ

Ễ

C S TOÁN H C Ố C A MÃ CH NG NHI U

ọ ủ

ơ ở

ố

ễ

C s toán h c c a mã ch ng nhi u

ọ ủ

ế ố ể ể ượ

ế

ồ ơ ở ế n 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ách xây n Các ki n th c này là r t quan tr ng đ hi u đ ố ạ ố c trình bày bao g m các c u trúc đ i s

ư ệ

ấ ườ GF(2) và ệ

Trang 2

t vào trong ễ ng ặ ố ệ ứ ọ ạ ự d ng các lo i mã kh i tuy n tính. ệ ượ n Các khái ni m đ ườ ặ nh nhóm, tr t là các tr ng và đ c bi ứ ụ ườ GF(2m), đây là các tr ng có ng d ng đ c bi ế ố ự vi c xây d ng các mã kh i tuy n tính ch ng nhi u.

ọ ủ

ơ ở

ố

ễ

C s toán h c c a mã ch ng nhi u

ệ

ơ ả

ứ

ườ GF(2)

ng

11.1 M t s khái ni m c b n 11.2 Tr 11.3 Tr

ộ ố ườ GF(2) và các đa th c trên tr ng ườ GF(2m) ng

Trang 3

ộ ố

ơ ả

ệ

M t s khái ni m c b n

n Phép toán đóng

n Cho G là m t t p h p, m t phép toán hai ngôi

ượ ọ ợ f đ c g i là

n Chú ý

ộ ộ ậ đóng trên G n u ế f có d ngạ G (cid:0) G ế a, b (cid:0) f : G (cid:0) ứ t c là n u G thì f(a, b) (cid:0) G.

afb và ng ượ ạ c l

ế ộ i ế f là phép c ng thì

ế ộ f(a, b) có m t cách vi ượ t là c vi t +(ế a, b) chúng ta th a + b.

n K t

f(b, a) còn đ thay vì vi ể ừ ươ ạ ng vi ộ ở ề ế đây tr v sau khi nói đ n m t phép toán n u chúng ta

Trang 4

ế ươ ng đ t t ng là ẳ bfa. Ch ng h n n u ườ t là ế không nói gì thêm thì có nghĩa là phép toán này có tính đóng.

ộ ố

ơ ả

ệ M t s khái ni m c b n (tt)

ượ ọ ế ợ f trên G đ c g i là có tính k t h p

ế ợ n Tính k t h p ộ n u ế (cid:0)

n M t phép toán hai ngôi a, b, c (cid:0)

G thì

(afb)fc = af(bfc)

n M t phép toán hai ngôi

n Tính giao hoán ộ n u ế (cid:0)

ượ ọ f trên G đ c g i là có tính giao hoán

G thì

n Ví dụ

a, b (cid:0) afb = bfa

ậ ố ự

ộ ừ

Trang 5

ế n 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.

Nhóm

n Tính phân ph iố n Phép toán f1 đ

ượ ọ ố ố ớ

f2 n u ế (cid:0) c g i là có tính phân ph i đ i v i phép toán G thì

a, b, c (cid:0) af1(bf2c) = (af1b)f2(af1c)

ẳ ố ố

n Ch ng h n trên t p s th c, phép nhân có tính phân ph i đ i R

(cid:0) ạ ớ v i phép c ng vì

n Nhóm

ộ a(cid:0) ậ ố ự a, b, c (cid:0) (b+c) = (a(cid:0) b)+(a(cid:0) c)

ộ ớ ượ ọ ộ , v i m t phép toán hai ngôi f đ c g i là m t

ộ ậ G (cid:0) n M t t p ế ề

Trang 6

ệ ế ợ (cid:0) ả nhóm n u tho 3 đi u ki n sau: f có tính k t h p. (1)

Nhóm (tt)

G thì afe = efa

ộ ố a (cid:0) ố ớ trung hoà (đ i v i m t s phép

ầ ử ơ c ượ = a. e đ toán e còn đ ầ ử e, sao cho (cid:0) ứ (2) G ch a ph n t ầ ử ọ g i là ph n t ượ ọ c g i là ph n t ị đ n v )

ầ ử ố ứ ứ đ i x ng, t c là

(cid:0) ạ ọ (3) M i ph n t i ph n t ầ ử ề ầ ử b (cid:0) đ u có ph n t G sao cho G, t n ồ t a (cid:0)

afb = bfa = e

ẳ ộ ạ n Ch ng h n, trên t p ậ R n u ế f là phép c ng thì ph n t trung

ầ ử ế f là phép nhân thì

ượ ọ ầ ử ơ ậ ố ự 1 và còn đ trung hoà là c g i là ph n t ị đ n v .

hoà là s ố 0, còn trên t p s th c khác 0 n u ầ ử ph n t n Nhóm giao hoán

n M t nhóm mà phép toán

ộ ượ ọ f có tính giao hoán thì đ c g i là

Trang 7

nhóm giao hoán.

Nhóm (tt)

ạ n Nhóm h u h n, nhóm vô h n

ữ ạ n M t nhóm có s ph n t

ộ

ầ ử ữ ạ ượ ọ h u h n đ ầ ử ố vô h n đ

c g i là nhóm ạ ượ ọ c g i

ố ộ ữ ạ h u h n, m t nhóm có s ph n t là nhóm vô h n.ạ

n Nhóm con

n Cho G là m t nhóm. M t t p

ộ ậ H con c a ủ G đ

ộ

ượ ọ c g i ế H đóng v i phép toán hai ngôi

ệ ủ

ả ề

ớ ộ

ộ là m t nhóm con n u c a ủ G và tho đi u ki n c a m t nhóm.

Trang 8

ộ

Phép c ng và nhân modulo

ộ

n Phép c ng modulo và phép nhân modulo

ự ộ ố n Cho m t s nguyên d ộ ậ ố ươ m xác đ nh. Xây d ng m t t p s ng

ư ọ ị ị ớ ớ (cid:0) ng. Đ nh nghĩa phép toán m i ộ nh sau và g i là phép

nguyên sau G = {0, 1, …, m –1}. V i + là phép c ng thông ườ th ộ c ng modulo

(cid:0) a, b (cid:0) G thì a (cid:0) b = (a + b) mod m

n T

ườ ự ớ (cid:0) v i là phép nhân thông th ng. Đ nh nghĩa phép

ươ ng t toán m i ớ (cid:0)

Trang 9

(cid:0) ị ư nh sau và g i là phép nhân modulo a, b (cid:0) b) mod m ọ G thì a (cid:0) b = (a (cid:0)

Ví dụ

n 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.ạ

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.

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.

n Hai b ng sau đây trình bày l n l

ầ ượ ườ ả t tr ng h p ợ m = 5 và m =

Trang 10

Ví d (tt)ụ

m = 5 m = 6

(cid:0) (cid:0) 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

n T

ươ

ớ ự ậ G = {1, …, m –1} v i phép nhân modulo và m Trang 11 ố ữ ạ ộ ng t nguyên t t p là m t nhóm giao hoán h u h n.

B đổ ề

ộ ố ố

ổ ề n B đ 11.1 n N u ế m là m t s nguyên t

thì

(cid:0) G = {1, …, m – 1} là m t ộ i n u . Ng ượ ạ ế m c l

ố ộ ớ nhóm giao hoán v i phép nhân modulo thì không nguyên t G không là m t nhóm.

m = 5 m = 6

(cid:0) (cid:0) 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

Trang 12

5 5 4 3 2 1

Tr

ngườ

n Tr

ạ ẳ ộ ậ G v i hai phép toán đóng hai ngôi b t k , ch ng h n

ượ ọ ộ ườ ề ả ấ ỳ ế ớ + và *, đ c g i là m t tr ng n u tho 3 đi u

ệ

ngườ n M t t p ệ kí hi u là ki n sau

ầ ử

ườ ượ trung hoà trong phép + th ố ớ (1) G là nhóm giao hoán đ i v i phép +. Ph n t ệ 0. c kí hi u là ng đ

ầ ử khác

ộ ườ ậ 0 là m t nhóm đ i v i ng đ ố ớ ượ ọ c g i là

(2) T p các ph n t ầ ử trung hoà trong phép * th ệ phép *. Ph n t ầ ử ơ ph n t ị đ n v và kí hi u là 1.

n Chú ý

ố ố ớ (3) Phép * có tính phân ph i đ i v i phép +.

ế ấ trên không nh t thi

ộ t là phép c ng và phép ấ ỳ ở ể ng mà chúng có th là b t k phép nào.

n Phép + và phép * ườ nhân thông th Trang 13 ư ậ ệ Chúng ta kí hi u nh v y đ d trình bày.

ể ễ

ườ

Tr

ng (tt)

n Các ph n t

ấ ế c a m t tr

ầ ử ủ ự ộ ườ ng không nh t thi ể ố t là các s ẳ ạ

ậ ứ

ng bao

ể trung hoà c a phép

ầ ử ệ + (kí 1). Các

ấ ộ ườ ng chúng ta suy ra m t tr ủ * (kí hi u là ố 0 và s ố 1 theo nghĩa ầ ử : ph n t ủ t là s

ể ẳ ạ ng mà có th là b t k cái gì ch ng h n là ma tr n ậ

n Tr

ơ ị, ...

ượ ọ * có tính giao hoán thì đ ng mà phép c g i là

Trang 14

ể ấ ỳ nguyên hay th c mà có th là b t k cái gì, ch ng h n có th ơ ố ứ , ma tr n hay đa th c ... là các s ph c, vect ườ ủ ừ ị n T đ nh nghĩa c a tr ầ ử ố ồ i thi u hai ph n t g m t ệ trung hoà c a phép 0) và ph n t hi u là ế ầ ử 0 và 1 không nh t thi ph n t ấ ỳ ườ thông th ậ 0 và ma tr n đ n v ườ ng giao hoán ộ ườ n M t tr ườ ng giao hoán. tr

ườ

Tr

ng (tt)

n 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.

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.

ộ ố

ổ ề n B đ 11.2 n Cho p là m t s nguyên t

ố ấ ỳ G = {0, 1, ..., p – 1} thì G là b t k ,

(cid:0) ố ớ ộ ng giao hoán đ i v i phép c ng modulo và phép

ộ ườ m t tr nhân modulo (cid:0)

n Tính ch t 1ấ ọ

ấ ủ ườ . ộ ố n Sau đây là m t s tính ch t c a tr ng

n M i ph n t

Trang 15

ủ ườ ề ầ ử a c a tr ng đ u tho ả a * 0 = 0.

ườ

Tr

ng Galois

n Tính ch t 2ấ

n N u ế a, b là hai ph n t

ầ ử ườ khác ủ 0 c a tr ng thì a * b (cid:0) 0.

n Tính ch t 3ấ n N u ế a (cid:0)

0 và a * b = a * c thì b = c. Hay nói cách khác n u ế a

(cid:0) 0 và b (cid:0) c thì a * b (cid:0)

a * c. ườ

ộ ườ

ng.

ng, tr ộ ườ c a m t tr ố ng có s ph n t

ữ ạ ườ ng h u h n, tr ậ ủ c g i là b c c a m t tr c g i là ạ ượ ọ

ộ ườ ượ ọ ng đ ầ ử ữ ạ ượ ọ h u h n đ ầ ử ố ng có s ph n t

ạ ng vô h n. ộ ườ ữ ng vô

n Tr

ườ ng h u ườ tr c g i là vô h n đ

ậ ủ n B c c a m t tr ầ ử ủ ố n S ph n t ộ ườ M t tr h nạ , m t tr h nạ . ườ GF(q) ng ộ ườ n M t tr

c g i là tr ườ ng ượ ầ ử ữ ạ ượ ọ h u h n đ q thì tr ng Galois là ườ ng đ c kí

ố ng có s ph n t ườ ậ ủ ế Galois. N u b c c a tr Trang 16 ệ GF(q). hi u là

ườ

Tr

ng Galois

ườ ườ ữ ạ ứ ng h u h n t c là tr ng Galois chúng ta có

ố ố ớ n Đ i v i các tr ị đ nh lý sau. ị n Đ nh lý 11.1 ộ ườ n M t tr pm

ầ ử ủ ng h u h n thì s ph n t ố còn ườ

ộ ố ố ạ ả c a nó ph i có d ng ộ ố m là m t s nguyên ạ ề ng Galois đ u có d ng ộ ố m là m t s còn

ươ

ữ ạ ộ ố trong đó p là m t s nguyên t ươ ng. Hay nói cách khác các tr d GF(pm) trong đó p là m t s nguyên t nguyên d ố ớ ố ng. n Đ i v i các tr thì đó chính là t p ườ GF(p) v iớ p nguyên t

(cid:0) ộ ậ và nhân

{0, 1, 2, ..., p – 1} v i hai phép toán c ng modulo modulo (cid:0) ố ớ ứ ạ ủ

ẽ ớ i thi u sau. Chú ý lúc này các ph n t

ơ ố

ng ớ ế ư nh đã bi ườ GF(pm), vì tính ph c t p c a chúng, ng n Đ i v i các tr ầ ử ủ ệ c a chúng ta s gi ạ ẽ ầ ườ GF(pm) không đ n thu n là các s mà s có d ng khá tr ng Trang 17 ệ ặ đ c bi t.

ườ

Tr

ng Galois (tt)

ầ ử ố ứ

n Kí hi u các ph n t

ượ ượ đ i x ng c a đ i x ng c a

đ i x ng ủ a trong phép + đ ủ a trong phép * đ

ệ c kí hi u là ệ c kí hi u là –a, a–1.

ừ ng giao hoán, t + và phép * chúng

ấ – và phép / nh sau (không nh t

ừ ườ

ệ ầ ử ố ứ n Ph n t ầ ử ố ứ ph n t n Phép – và phép / ố ớ n Đ i v i m t tr ị ế t là phép tr và phép chia bình th

ộ ườ ta đ nh nghĩa thêm hai phép thi hai phép ư ng)

a – b = a + (–b)

a / b = a * b–1

ầ ử ố ứ ủ b qua phép +,

trong đó –b là ph n t ầ ử ố ứ còn b–1 là ph n t đ i x ng c a đ i x ng c a ủ b qua phép *.

n 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

ộ ườ

ị

ủ Tr riêng c a m t tr

ng

n Xét m t tr

ầ ử ơ ủ ổ ộ ườ GF(q). Xét các dãy t ng c a các ph n t đ n ng

ầ

(k l n, v i

ớ k = 1, 2, 3, …)



vị (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

111 1

(cid:0)

n Vì tr

ườ ả ủ ổ

ể

ườ ữ ng đóng v i phép c ng nên k t qu c a nh ng t ng ạ ậ k có th nh n vô h n ị k1 và ồ ạ i hai giá tr

(cid:0) này cũng là các ph n t ị giá tr mà tr k2 khác nhau (gi ỉ ng ch có s (cid:0) (cid:0)

(cid:0) (cid:0) ộ ớ ế ườ ầ ử ủ c a tr ng. Vì ầ ử q ph n t nên t n t k k 1 2 ả ử k1 > k2 ) sao cho 1 1 1 1

k 1

n T đây suy ra

(cid:0) ừ

(cid:0) (cid:0)

k 2 1 1

Trang 19

(cid:0)

ộ ườ

ị

ủ Tr riêng c a m t tr

ng

n Tr riêng c a m t tr

ộ ườ ệ ố ươ ng kí hi u là s nguyên d ỏ ng nh (cid:0) ị nh t ấ (cid:0) ủ sao cho (cid:0) (cid:0)

ố ớ ễ ấ

01 (cid:0)i 1 ng ị thì tr riêng

(cid:0) ố ộ ố ườ GF(p) = {0, 1, 2, ..., p – 1} v i ớ p ổ = p. T ng quát chúng ta có

n D th y đ i v i các tr là m t s nguyên t ị đ nh lý sau. ị n Đ nh lý 11.2 ị n Tr riêng n Ch ng minh

(cid:0) ủ ộ ố c a m t tr ộ ườ GF(q) là m t s nguyên t ng ố .

ứ n Gi

= k (cid:0) ố (cid:0)

Trang 20

l (k, l nguyên > 1). T ừ ộ không nguyên t ố ủ ả ử (cid:0) s ắ ố ớ (cid:0) qui t c phân ph i c a phép nhân đ i v i phép c ng suy ra

ộ ườ

ị

ủ Tr riêng c a m t tr

ng (tt)

(cid:0) (cid:0)

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

1 1

lk 1 1

1 1

1 1 l

(cid:0) (cid:0) (cid:0) (cid:0)

01 Suy ra 1

01 1

(cid:0) (cid:0)

ho cặ

ề Mà k, l < (cid:0) , đi u này

n Chu k c a m t ph n t

ẫ ủ (cid:0) ớ ị mâu thu n v i đ nh nghĩa c a .

ộ ỳ ủ ộ n Xét m t ph n t

ủ 0 c a tr ng

ườ ớ

ầ ử ấ ỳ ầ ử a b t k khác ỹ ừ ak c a ủ a v i ớ k = 1, 2, 3, … Vì tr

(cid:0) (cid:0) (cid:0) ậ ạ ườ GF(q). Xét các ng đóng v i phép k có th ể ồ ạ nên t n t i hai

Trang 21

lu th a ườ ầ ử ủ nhân nên các ak cũng là các ph n t c a tr ng. Vì (cid:0) k k k ka 1 2 1 2 ầ ử ỉ ườ ị q ph n t nh n vô h n giá tr mà tr ng ch có 1 ả ử k1 > k2 ) sao cho giá tr ị k1 và k2 khác nhau (gi s

ỳ ủ

ầ ử

ộ

Chu k c a m t ph n t

n Chu k c a m t ph n t ươ

ỳ ủ ộ ủ ầ ử a c a m t tr ộ ườ GF(q) là s ố ng

n Ví dụ

ỏ ng nh nh t nguyên d ấ n sao cho an = 1.

n Xét tr ị

(cid:0) ườ GF(7) = {0, 1, 2, 3, 4, 5, 6} v i hai phép .

ủ và (cid:0) ớ ầ ử ỳ ủ 7. Còn chu k c a các ph n t ả ng này là ượ ng ủ Tr riêng c a tr ườ khác 0 c a tr c trình bày trong b ng sau ườ ng đ

2 3 4 5 6

Ph n tầ ử 1 Chu kỳ 1 3 6 3 6 2

ừ ị ấ ỹ ừ ủ a n T đ nh nghĩa trên chúng ta th y dãy các lu th a c a

a1, a2, ..., ak, ..., an = 1, an+1 = a, ...

ầ ử i sau n ph n t .

ẽ ặ ạ s l p l Trang 22

ầ Nhóm tu n hoàn

ớ ộ

ổ ề n B đ 11.3 ạ n Dãy a1, a2, ..., ak, ..., an = 1 t o nên m t nhóm con đóng v i ườ GF(q).

phép nhân trên tr ầ n Nhóm tu n hoàn

n M t nhóm (không ch a ph n t

ộ * đ

ầ ừ ủ ừ ị ữ ạ ượ ọ ầ c g i là tu n

ỳ trong nhóm có chu k đúng

ộ ầ ử ủ ượ ọ ớ ầ ử 0) v i phép nhân ứ c g i ế ồ ạ ỹ ầ ử ộ i m t ph n t là tu n hoàn n u t 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. ộ n T đ nh nghĩa này suy ra m t nhóm h u h n đ ầ ử i m t ph n t c a nhóm.

ế ồ ạ hoàn n u t n t ố ằ b ng s ph n t n Đ nh lý 11.3

ầ ử ủ khác 0 c a m t tr ộ ườ GF(q) thì ng

ị ộ n N u ế a là m t ph n t aq–1 = 1 Trang 23

ầ Nhóm tu n hoàn (tt)

ứ

n Ch ng minh

n G i ọ b1, b2, ..., bq1 là q – 1 ph n t

khác nhau và khác 0 c a ủ

ườ ườ ng. Theo tính ch t ng chúng ta có

khác nhau và

ườ ủ ầ ử ủ ấ 3 và tính ch t ấ 2 c a tr tr ầ ử a*b1, a*b2, ..., a*bq1 cũng là q – 1 ph n t khác 0 c a tr ng. Vì v y chúng ta có

ậ a*b1*a*b2* ... *a*bq1 = b1*b2* ... *bq1

ấ ứ aq–1 = 1. Hoàn t t ch ng minh.

ầ ử ấ ỳ ủ b t k khác 0 c a m t tr ộ ườ GF(q) ng

Trang 24

ừ n T đây suy ra ị n Đ nh lý 11.4 ộ ỳ ủ n Chu k c a m t ph n t ướ ố ủ q – 1. c s c a là

ầ ử ơ ở

Ph n t

c s

ứ

n Ch ng minh

ỳ ủ ủ ầ ử a khác 0 c a tr ườ GF(q). Gi ng

n G i ọ n là chu k c a ph n t s ử q – 1 không chia h t cho ế là s d c a phép chia

ả n. Do đó q – 1 = kn + r, trong đó r

q – 1 cho n, 0 < r < n. Chúng ta có

ố ư ủ aq1 = akn+r = (an)k*ar

ề Do aq1 = 1 và an = 1 suy ra ar = 1. Mà 0 < r < n đi u này

ẫ ớ ị ỳ ủ a. V y ậ q – 1 chia h t ế

mâu thu n v i đ nh nghĩa chu k c a cho n.

ượ ọ

ầ ử ơ ở

c s n M t ph n t

c g i là

ầ ử a khác 0 c a m t tr c s n u chu k c a q – 1.

n Ph n t ộ ộ ườ GF(q) đ ủ ng ầ ử ơ ở ế ỳ ủ a b ng ằ ph n t ộ n u ế a là m t ph n t ừ ị n T đ nh nghĩa này ừ ủ a g m ồ a0 = 1, a1 = a, a2, …, aq – 2 hình thành nên q

Trang 25 ầ ử

(cid:0) ầ ử ơ ở ỹ c s thì các lu

ườ th a c a – 1 ph n t khác ủ 0 c a tr ng.

Ví dụ

ặ c s c a

ườ GF(7) nh trong ví d ư ề ườ ủ ầ ử ng đ u là 0 c a tr ỳ ằ ầ ử 3 và 5 có chu k b ng ụ ở slide 211. Chu k c a các ỳ ủ ệ ướ ố ủ 6. Đ c bi t các ầ ử ơ c 6 nên chúng là các ph n t

ng n Xét tr khác ph n t ph n t ở ủ s c a tr ườ GF(7). ng

31 = 3 32 = 2 33 = 6 34 = 4 35 = 5 36 = 1

51 = 5 ng

ườ ườ ng ụ ề ứ ế 53 = 52 = 6 4 ng Galois thì tr ng có nhi u ng d ng đ c bi ườ GF(2m) t trong lý thuy t

Trang 26

ẽ ỉ 56 = 55 = 54 = 1 3 2 ườ GF(2) và tr n Trong các tr ặ ữ là nh ng tr ườ mã, nên chúng ta s ch trình bày hai tr ệ ng này.

Tr

ườ GF(2)

ng

n Tr

ồ ộ

ườ GF(2) ng n 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

n Ph n t

ầ ử ố ứ đ i x ng c a 0 và

ộ ủ 0 và 1 qua phép c ng cũng chính là ủ 1 qua phép nhân cũng chính là 1.

ớ ộ 1. Ph n t n Trong tr

ầ ử ố ứ đ i x ng c a ng ộ ố ừ ố ườ GF(2) thì phép tr gi ng v i phép c ng, phép ố ớ 0 cũng gi ng v i phép nhân.

chia cho m t s khác Trang 27

ứ Các đa th c trên tr

ườ GF(2)

ng

ườ GF(2)

ng

ứ n Đa th c trên tr ộ

ứ ệ ạ ẳ ườ GF(2), ch ng h n kí hi u là ng f(x), là

n M t đa th c trên tr đa th c có d ng

ứ ạ

f(x) = a0 + a1x + a2x2 + … + anxn ệ ố ai (cid:0) trong đó các h s GF(2).

ậ ớ ứ

ứ ậ ủ n B c c a đa th c ấ ủ n Là b c l n nh t c a đa th c.

n Ví dụ

n Đa th c ứ f(x) = 1 + x + x3 có b c ậ 3 đa th c ứ g(x) = x + x2 + x5

Trang 28

có b c ậ 5.

ứ Các đa th c trên tr

ườ GF(2) (tt)

ng

ộ

ứ ứ n Phép c ng đa th c và nhân đa th c

n V i ớ f(x) = a0 + a1x + a2x2 + … + anxn, g(x) = b0 + b1x +

ộ ớ ệ ố ai và bj thu c tr ườ GF(2) ng

ứ ứ ị

b2x2 + … + bnxn v i các h s ộ chúng ta đ nh nghĩa các phép c ng đa th c và nhân đa th c nh sauư

i x

)

(

(cid:0) (cid:0)

(cid:0)

i x

)

(

(cid:0) (cid:0)

ib 0 f(x) + g(x) = jbia * 0 f(x) * g(x)

(cid:0)

Trang 29

ượ ự trong đó ai + bi và ai * bj đ ệ c th c hi n trên tr ườ GF(2). ng

ứ Các đa th c trên tr

ườ GF(2) (tt)

ng

n Ví dụ

n Cho f(x) = 1 + x + x3, g(x) = x + x2 thì

f(x) + g(x) = (1 + x + x3) + (x + x2) = 1 + x2 +

f(x) * g(x) = (1 + x + x3) * (x + x2) = x + x3 +

x4 + x5

ể 0 thì chúng ta có th chia f(x) cho g(x)

n N u ế g(x) có b c khác ậ ư ể ế t nh sau f(x) = q(x) * g(x) + r(x)

và có th vi

trong đó q(x) là đa th c th ng còn r(x) là đa

Trang 30

n Ví dụ

n f(x) = 1 + x + x4 + x5 + x6 chia cho g(x) = 1 + x + x3

ứ ư ỏ ơ ứ ậ ứ th c d có b c nh h n đa th c chia ươ g(x).

ứ Các đa th c trên tr

ườ GF(2) (tt)

ng

n 1 + x + x4 + x5 + x6 = (x2 + x3) * (1 + x + x3) + (1 + x + x2) ạ ố n Đ 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 N u ế f(a) = 0 thì f(x) chia h t cho (x a). ườ GF(2). ng n Đi u này cũng đúng trên tr

ề n Ví dụ

n f(x) = 1 + x + x3 + x5 có f(1) = 0, nên f(x) chia h t cho ộ

ế

ừ (x 1) ứ ườ GF(2), phép tr cũng chính là phép c ng t c ng

ế mà trong tr là f(x) chia h t cho (x + 1).

Trang 31

1 + x + x3 + x5 = (1 + x)(1 + x3 + x4)

ứ ố ả

Đa th c t

i gi n

n M t đa th c trên

ộ ượ ọ ả ố GF(2) đ c g i là t

ỏ ơ ế ậ ủ ứ ượ phân tích đ i gi n n u nó không ứ 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 + x5 + x6

1 + x + x3 + x4 + x5

Trang 32

1 + x + x4

1 + x2 + x3 + x4 + x5 1 + x + x2 + x5 + x6

1 + x3 + x4 1 + x2 + x3 + x5 +

1 + x + x2 + x3 + 1 + x + x4 + x5 +

x4 x6

1 + x2 + x4 + x5 +

B đổ ề

ộ n Cho f(x) là m t đa th c trên tr ng

ứ n 2 ườ GF(2), thì 2 (cid:0) f f )x( x( )

ứ

n Ch ng minh n Đ t ặ f(x)

= a0 + a1x + … + anxn. [f(x)]2 = (a0 + a1x + … + anxn)2

… + anxn) + = a02 + a0*(a1x + … + anxn) + a0*(a1x + (a1x + … + anxn)2

= a02 + (a1x + … + anxn)2

= a02 + (a1x)2 + … + (anxn)2

Trang 33

= f(x2) (vì trong GF(2) ai2 = ai )

n Đi u này cũng giúp chúng ta suy ra đi u ph i ch ng minh.

ứ ề ề ả

Tr

ườ GF(2m)

ng

n Tr

(cid:0)ma

ướ ế ệ c h t chúng ta kí hi u tr ườ GF(2m) nh sauư

ng GF(2m) = {0, 1, a1, a2, ..., } trong đó 0 và 1 (cid:0)

2 2 ườ GF(2) là m t ộ GF(2). Tr ng ơ ở ủ ườ ng c s c a c g i là tr

ượ ọ ng con c a ủ GF(2m) và đ

n Chú ý

ườ tr GF(2m).

n N u ế a là m t ph n t

ộ ứ GF(2m), f(x) là m t đa th c trên

tr ng ầ ử ủ GF(2m).

ữ ạ ỉ

ạ n Có vô h n đa th c ầ ử (cid:0) ầ ử (cid:0) ườ GF(2), thì f(a) cũng là m t ph n t ứ f(x) trên tr GF(2m), nên (cid:0) ộ ng a (cid:0)

ặ f(x) = f1(x) – f2(x) (chú ý trong tr Trang 34 ớ ộ ộ c a ườ GF(2) mà ch có h u h n ồ ạ 0 c a ủ GF(2m) t n t (2m) ph n t i hai ừ đa th c ứ f1(x) và f2(x) khác nhau sao cho f1(a) = f2(a). T đây ườ GF(2) thì phép ế n u đ t ố – gi ng v i phép c ng +) thì f(a) = 0.

ứ ố

ể

Đa th c t

i thi u

ứ ố

ể

n Đa th c t

ầ ử ộ ứ ố

i thi u (minimal polinomial) ng khác

n Cho a là m t ph n t

ủ 0 c a tr ườ GF(2m). Đa th c t

i ườ GF(2) và có b c ậ ng

ằ

ể ủ a là đa th c ứ f(x) khác 0 trên tr thi u c a ỏ ấ f(a) = 0. nh nh t sao cho ả ộ ầ ữ n M t l n n a ta ph i chú ý r ng khi chúng ta vi ấ ế ố t là các s

ế f((cid:0) ) = 0 t ho c ặ f((cid:0) ) = 1 thì các kí hi u ệ 0 và 1 không nh t thi ẽ ượ 0 và 1, mà s đ ế ữ ả ậ ẳ 0 chính là ma

Trang 35

ể c hi u tu theo ng c nh. ầ ử (cid:0) ộ ạ n Ch ng h n n u ph n t ơ ỳ là m t ma tr n thì ị. ậ tr nậ 0 còn 1 chính là ma tr n đ n v

ứ ố

Đa th c t

ể i thi u (tt)

(cid:0) (cid:0)

0 0

1 0

0 1

0 0

(cid:0) (cid:0)

n Ví dụ ẳ

n Ch ng h n n u

44T

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) ạ ậ ế a là ma tr n 4 4 bên (cid:0) (cid:0)

(cid:0) (cid:0)

0 1

0 0

1 0

(cid:0) (cid:0)

ậ

ằ ự

ự ộ trong đó các phép c ng và nhân trên ma tr n ộ ớ ườ ng v i chú ý r ng các phép c ng ườ ệ ậ ượ c th c hi n trên tr ng c a ma tr n đ

ư ệ ẫ v n th c hi n nh bình th ầ ử ủ và nhân các ph n t GF(2).

ằ

ể ể n 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

Trang 36

ậ tr n 0.

n Và f(x) = 1 + x + x4 là đa th c t

ứ ố ể ủ a i thi u c a

ị

Đ nh lý

n 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à

n Đ nh lý 11.5

chu k c a ỳ ủ a.

ị n Cho a là m t ph n t

ủ 0 c a tr khác ườ GF(2m) có b c c a

ứ ố ậ ủ ầ ử ầ ử ộ i thi u c a ng ậ ấ ả ể ủ a là k. G i ọ Z là t p t t c các ph n t có

đa th c t d ngạ

ủ b0 + b1a + … + bk1ak1 trong đó bi (cid:0)

Trang 37

GF(2). Thì Z là m t t p con c a ộ ườ GF(2m) và hình thành nên m t tr ộ ậ ầ ử 2k ph n t ng có .

ứ

Ch ng minh

n Đ u tiên chúng ta ch ng minh các ph n t ằ

ầ ầ ử ượ ứ đ

ứ

ế ừ c hình thành t b0 + b1a + … + bk1ak1 là khác nhau b ng cách ch ng minh các ph n t ầ ử 1, a, a2, …, ak1 là đ c l p tuy n tính.

(cid:0) (cid:0)

(cid:0) (cid:0) (cid:0) ế ậ ậ Th t v y n u k 1 i ab i ộ ậ 1 ac i

(cid:0) (cid:0)

(cid:0) thì

ap )(

1 b ( i

ac ) i

(cid:0) (cid:0) (cid:0) (cid:0)

(cid:0)

V y chúng ta có đa th c ỏ ơ k

ậ ủ ứ ố ứ p(x) có b c nh h n ậ ể ủ a b ng ằ i thi u c a k.

Trang 38

ậ thoã p(a) = 0. Mà b c c a đa th c t V y ậ p(x) = 0, suy ra bi = ci (cid:0) i = 0, 1, ..., k – 1.

ứ

Ch ng minh (tt)

n Th hai, rõ ràng

ứ ố ớ +.

ộ Z là m t nhóm giao hoán đ i v i phép ậ ậ

(cid:0) (cid:0) (cid:0) (cid:0)

1 (

1 b ( i

ac ) i

ab ) i

1 ab i

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) ế Th t v y n u k 1 ac i

(cid:0) (cid:0) (cid:0) (cid:0)

ể ứ ộ Đ ch ng minh t p

(cid:0) (cid:0) (cid:0) (cid:0)

1 ac i

1 ab i

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) ậ Z0 = Z – {0} là m t nhóm ế ứ ố ớ * chúng ta ch ng minh n u đ i v i phép nhân k k 1 k ac i

(cid:0) (cid:0) (cid:0) (cid:0)

i x

x )(

(cid:0) (cid:0)

(cid:0)

0 G i là đa th c t

ứ ố ể ủ i thi u c a

ọ Trang 39 ệ ố a, trong đó h s

cao nh t ấ dk = 1.

ứ

Ch ng minh (tt)

(cid:0)

k T đây suy ra

1 d

ừ (cid:0) (cid:0)

(cid:0)

(cid:0) (cid:0) ễ Do đó m i ọ an v i ớ n (cid:0)

ộ thông qua m t đa th c (cid:0) (cid:0)

(cid:0) (cid:0) ề k ứ g(a) nào đó có b c ậ (cid:0) 0 ể ể k đ u có th bi u di n k 1 1 k – 1. Vì v y ậ ab ac * i i 0 (cid:0) (cid:0)

i Z

1 ac i

(cid:0) (cid:0) (cid:0)

1 ab i ậ cũng v y. Suy ra 0 0

(cid:0) (cid:0)

(cid:0) (cid:0) (cid:0) (cid:0)

1 ab i

1 ac i

1 i ab

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

1 i ac Và rõ ràng n uế 0

Trang 40

(cid:0) (cid:0) (cid:0) (cid:0)

ượ ế ừ ừ ườ ấ Tính ch t này đ c k th a t tr ng

GF(2m).

ả

H quệ

n Cu i cùng tính phân ph i c a phép nhân

ố ộ

ố ớ ứ * đ i v i phép c ng ế ừ ừ ườ GF(2m). Ch ng minh hoàn ố ủ tr ng

ể ủ

ườ GF(2m) có b c b ng c a

Z trùng v i tr ể ượ ư ộ + chúng ta cũng k th a t t.ấ t ệ ả n H qu 11.1 ứ ố ế n N u đa th c t m thì tr ng ườ tr ng có th đ ầ ử a (cid:0) i thi u c a ph n t ng c bi u di n nh m t vect ậ ằ ầ ử ủ ơ m thành ph nầ ỗ

n Đ nh lý 11.6

ớ ườ GF(2m) và m i ph n t ễ ể (b0b1…bm1)

ứ ố ể ủ ườ

ị n G i ọ f(x) là đa th c t

i thi u c a ph n t ng

Trang 41

ứ ố ả GF(2m) thì f(x) là đa th c t ầ ử a (cid:0) ườ i gi n trên tr ủ 0 c a tr ng GF(2).

ứ

Ch ng minh

n Gi

ậ ớ ơ s

ỏ ơ ả ử f(x) = g(x) * h(x) trong đó g(x) và h(x) có b c l n h n ậ ủ f(x). Chúng ta có f(a) = g(a) * h(a) = 0,

ớ ị ẫ

ứ ố ề ể ủ a. i thi u c a

ườ 0 và nh h n b c c a 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 ổ ể n B đ 11.5 n Cho f(x) là đa th c t ầ ử a (cid:0)

ủ 0 c a tr ng ườ GF(2) sao cho ng

ể ủ ứ ấ ỳ ế f(x).

n Ch ng minh

n Chia p(x) cho f(x) chúng ta đ

ứ ố i thi u c a ph n t GF(2m) và p(x) là đa th c b t k trên tr p(a) = 0. Thì p(x) chia h t cho ứ

cượ

p(x) = g(x) * f(x) + r(x)

ỏ ơ ậ ủ r(x) nh h n b c c a

ậ ủ f(x). ủ đ nh nghĩa c a đa

ế ứ ố trong đó b c c a Thay x = a (cid:0) r(x) = 0 (cid:0) ừ ị r(a) = 0, nên t p(x) chia h t cho f(x). th c t

ể (cid:0) i thi u Trang 42

ị

Đ nh lý

n Đ nh lý 11.7

ể ủ ườ ứ ố i thi u c a ph n t ng ầ ử a (cid:0)

ị n Cho f(x) là đa th c t

ứ ố ả ườ GF(2) sao cho i gi n trên tr ủ 0 c a tr ng

GF(2m) và p(x) là đa th c t p(a) = 0. Thì f(x) = p(x). ứ

n Ch ng minh ổ ề chúng ta có th vi

n Theo B đ 11.5 trên chúng ta có ể ế t

ế p(x) chia h t cho ứ f(x) t c là

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) =

ầ ử ủ ệ ủ 0 c a tr (cid:0)m 2 1 (cid:0) (cid:0) ươ ph ề ườ GF(2m) đ u là nghi m c a 1 khác x ng 0

f(x) = p(x). Tuy nhiên f(x) không th b ng 1 nên suy ra p(x). ệ ả n H qu 11.2 n 2m – 1 ph n t ng trình Trang 43

ả

H quệ

(cid:0) ứ ố ể ủ ầ ử i thi u c a các ph n t

ả ệ n H qu 11.3 (cid:0)m 2 11 ế n chia h t cho các đa th c t x ủ khác 0 c a tr ng

ả ạ ẽ ẫ ư ơ ướ c

ế h t chúng ta phân tích ườ GF(2m). ộ ệ n Chúng ta s d n ra m t h qu m nh h n nh sau. Tr (cid:0)m (cid:0)

(cid:0)m

ứ ố ả ườ i gi n trên tr ng

11 ủ thành tích c a các đa th c t 11

(cid:0)m

(cid:0)

(cid:0) GF(2) 2 x

= p1(x) * p2(x) * … * pl(x) ầ ử ủ c a

ườ GF(2m) nên các ph n t Vì có các nghi m là các ph n t c a tr

ng ệ ủ ấ ỳ ộ pi(x) b t k

ầ ử ủ tr ộ pi(x) nào đó và ng nghi m c a m t ầ ử ủ ệ ẽ s có các nghi m là các ph n t

ệ ườ GF(2m) s là ẽ ng ượ ạ c l i m t ườ GF(2m). ng c a tr ơ ữ ế pi(x) có b c ậ t thì s có ẽ H n n a n u t nghi m ệ

Trang 44 ườ GF(2m). ng

trong tr

ả

H quệ

ả

(cid:0)m

n H qu 11.4 ệ

(cid:0) ể i

ệ n Trong vi c tri n khai thành tích các đa th c t ể ủ

11 ả ẽ

ứ ố ộ ứ ố i thi u c a m t

2 x ả ứ ố ỗ gi n, thì m i đa th c t ầ ử ph n t 0 nào đó c a tr khác n Đ nh lý 11.8

i gi n s là đa th c t ủ ng ườ GF(2m).

ầ ử ủ 0 c a tr ườ GF(2m) và f(x) là ng

ộ

ị ộ n Cho a là m t ph n t ứ m t đa th c trên tr

)

khác ng

ườ GF(2). N u ế f(a) = 0 thì ( 2l af l = 0, 1, 2, ...

= 0 (cid:0) ả n H qu 11.5

ứ ố

ệ n N u ế f(x) là đa th c t

ủ 0 c a tr ng

i thi u c a ph n t ứ ố ầ ử a (cid:0) ể ủ ườ ầ ử i thi u c a các ph n t

ể ủ GF(2m) thì f(x) cũng là đa th c t l

a 2 Trang 45

ủ v i ớ l = 0, 1, 2, ... c a tr ườ GF(2m). ng

ệ

ả

H qu (tt)

ứ ố ủ nghi m c a đa th c t ớ l = 0, 1, 2, ... là các ầ ử a.

ệ ơ ữ ẽ ứ ầ ử n Hay nói cách khác các ph n t i thi u n H n n a chúng ta s ch ng minh r ng ngoài chúng ra f(x)

a 2 v i ủ ể f(x) c a ph n t ằ không còn nghi m nào khác thu c tr l

ệ ộ ườ GF(2m). ng

n Vì v y n u có bao nhiêu ph n t

a 2 khác nhau thì

ầ ử ế f(x) có

ươ ấ ỏ ng nh nh t sao

ậ ậ ấ b c b y nhiêu. ề ể cho (cid:0) ố ọ k là s nguyên d n Đ làm rõ đi u này g i 2 a a

m m 2 1 S ố k ch c ch n t n t ắ ồ ạ i vì chúng ta đã có hay a a 1

(cid:0) ắ (cid:0) (cid:0)

Trang 46

ỳ ủ ể ễ Và s ố k bi u di n chu k c a dãy a 2

v i ớ l = 0, 1, 2, ...

B đổ ề

ườ GF(2m) và k là s ố ng

ổ ề n B d 11.6 ầ ử n Cho a là m t ph n t ỏ

ộ ươ nguyên d

(cid:0)

a 2

ủ 0 c a tr khác ấ ng nh nh t sao cho 2 a a ộ ướ ố ủ m. c s c a thì k là m t

ứ

n Ch ng minh

r < k

hay a a

k + r, trong đó r là s d và k 2 (cid:0) (cid:0) Chia m cho k, m = n (cid:0) k ố ư k 22 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

(cid:0) (cid:0)

(cid:0)

ặ (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) ể rkn (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) ế ụ Ti p t c theo ki u này chúng ta có . M t khác m r 2 chúng ta có a a

a Trang 47

(cid:0) (cid:0)

ổ ề B đ (tt)

ấ ứ ị r = 0. Hoàn t t ch ng minh. ủ k (cid:0)

ầ ử

n Ph n t

ườ GF(2m) và k là s ố ng

Do đ nh nghĩa c a ợ liên h p ộ ươ nguyên d

(cid:0) ủ khác 0 c a tr ấ ng nh nh t sao cho 2 a

ượ ọ ớ l = 0, 1, 2, ..., k 1 đ v i

ượ ọ ầ ử ợ ố c g i là s ph n t c g i là các liên h p ầ ử n Cho a là m t ph n t ỏ l a 2 ầ ử thì các ph n t ợ ủ a và k đ ầ ử liên h p c a

liên h p c a ợ ủ a là

ấ ậ ượ ầ ử ph n t c a ủ a. ừ ị ậ t p các ph n t ầ ử n T đ nh nghĩa chúng ta th y t p các ph n t ở c sinh ra b i khác nhau đ a 2

Trang 48

v i ớ l = 0, 1, 2, ...

ầ ử

ổ ề n B d 11.7 n N u ế a1 và a2 là các ph n t

ấ ỳ ủ a thì a1 là ợ ầ ử liên h p c a ợ ủ a2 và ng liên h p b t k c a ượ ạ a2 là ph n t i liên h p ợ c l

ầ ử ph n t c a ủ a1.

ổ ề B đ (tt)

ố ậ ậ n Th t v y gi ả ử ớ k là s ph n t liên h p c a ợ ủ a)

a 1

l 1

s (v i l 12 ầ ử l 22 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

l 1

l l 2212

l 22

l l 2212 )

(

a 1

(cid:0) (cid:0) (cid:0) (cid:0) Thì l 22 (cid:0) (cid:0) (cid:0) (cid:0)

lk 1

l 222

l 222 )

(

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) và 2 a 2

lk 1

l 12

(cid:0)

)

(

a 1

(cid:0) (cid:0) (cid:0) (cid:0)

ứ t ch ng minh. Hoàn t

n Chú ý b đ này nói lên r ng các ph n t

ầ ử ằ liên h p c a ợ ủ a là

ợ ấ Trang 49 ổ ề ớ liên h p v i nhau.

ổ ề B đ (tt)

n Vì các ph n t

ủ ớ l = 0, 1, 2, ..., k 1 là các nghi m c a

ứ ố

l a 2 ệ ầ ử v i ể f(x) c a ủ a, nên ta s ch ng minh f(x) có i thi u 1

(cid:0) (cid:0) ẽ ứ k 1



(*)

)

(

)

(

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) đa th c t d ngạ x f )(

(cid:0)

n Đ ch ng minh đi u này chúng ta s ch ng minh

(

i ẽ ứ 2 )

ể ứ (cid:0) (cid:0) (cid:0) ề x p )(

(cid:0)

ứ ố ộ ả ị là m t đa th c t i gi n và do p(a) = 0 nên theo Đ nh lý

Trang 50

11.7 chúng ta suy ra f(x) = p(x).

ổ ề B đ (tt)

ườ GF(2m) và k là s ố ng

ổ ề n B d 11.7 ầ ử n Cho a là m t ph n t ỏ

ộ ươ nguyên d ủ 0 c a tr khác ấ ng nh nh t sao cho

(cid:0)

a k

(cid:0)

x )(

i 2 )

(

(cid:0) (cid:0) thì (cid:0)

(cid:0)

ứ ố ộ là m t đa th c t

ng 2 (cid:0) (cid:0) (cid:0) (cid:0) i gi n trên tr k ườ GF(2). k ả 1

ứ

n Ch ng minh p

x )(

)

(

)

(

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

Trang 51

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

ứ

Ch ng minh (tt)

(cid:0)

)

(

)

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

(cid:0) (cid:0)

x )(

(

)

(

)

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

(cid:0) (cid:0)

i k

0 1

(cid:0)

(

)(

)

(cid:0) (cid:0) (cid:0) (cid:0)

(cid:0)

i k

1 1

(cid:0) (cid:0)

(

)(

)

(

)

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

(cid:0) (cid:0)

(

)

Trang 52

(cid:0)

ứ

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

x b 1

b ( 0

ườ ứ ầ ử ủ c a tr ng (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) ườ GF(2) c a ủ a. Vì v y các bi là các ph n t 2 ) ậ  b k p(x) = b0 + b1x + … + bkxk trong đó các bi v i ớ i = 0, 1, 2, …, k là các đa th c trên tr ng k x p )( GF(2m).

i 22 x

i x

22 x

)11(

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

b i 0

(cid:0) (cid:0) (cid:0) (cid:0)

bb i 0 i

(cid:0)

i = 0, 1, 2, …, k

ế ằ ặ ầ ử 0 ho c ph n

ầ ườ ứ ộ Do [p(x)]2 = p(x2) suy ra bi = bi2 (cid:0) Trang 53 ề ỉ Đi u này ch đúng n u các bi (cid:0) ứ ử 1 t c là các t bi b ng ph n t GF(2) hay p(x) là m t đa th c trên tr ng

GF(2).

ứ

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 q(a) = 0 ho c ặ h(a) = 0. p(a) = 0 (cid:0) Nh ng do ậ ủ p(x) là k. a 2

ệ s (cid:0) ả ử q(a) = 0, theo Đ nh lý 12.8 q(x) có các nghi m là

ể i thi u là k, m u ẫ

n Đ nh lý 11.9

ị Gi v i ớ l = 0, 1, 2, ..., k – 1, (cid:0) ẫ q(x) có b c t ứ ả ừ ề ậ ố thu n. T đây suy ra đi u ph i ch ng minh.

ườ GF(2m) và k là s ố ng

(cid:0)

ị ầ ử n Cho a là m t ph n t ỏ

ộ ươ nguyên d ủ khác 0 c a tr k 2 ấ ng nh nh t sao cho a a (cid:0)

x )(

(

i 2 )

(cid:0) (cid:0) (cid:0)

(cid:0)

ứ ố thì đa th c t Trang 54 i thi u c a ể ủ a là và có b c ậ

= k.

ả

H quệ

n H qu 11.6

ộ i thi u c a m t ph n t ầ ử a khác 0 c a ủ

ả ệ ứ ố ộ ậ ủ n B c c a m t đa th c t ườ GF(2m) là m t ng

n Đ nh lý 11.10 ộ

tr ể ủ c s c a ộ ướ ố ủ m.

ủ 0 c a tr ng

ỳ ằ

ị ầ ử n Cho a là m t ph n t ầ ử n thì các ph n t

a 2 ườ GF(2m) có chu k ỳ ợ ủ a cũng có chu k b ng n.

khác liên h p c a

b ng ằ ứ n Ch ng minh ố

n G i ọ k là s thành ph n liên h p c a i

(

)

ầ n (cid:0) (cid:0) i = 0, 1, ..., k i (cid:0) ợ ủ a. (cid:0) ni (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

(cid:0) (cid:0)

n Chúng ta ch ng minh r ng không

(cid:0) ứ ằ ố ươ s nguyên d ng l < n

(cid:0) (cid:0)

(cid:0) (cid:0) (cid:0)

Trang 55

(cid:0) (cid:0)

ứ

Ch ng minh

i a i, suy ra

(cid:0) (cid:0) ả ử ồ ạ s t n t

l cho n

n + r

rnh

(

hn )

ậ ậ Th t v y gi Chia 2i (cid:0) l = h (cid:0) 2i (cid:0) trong đó 0 (cid:0) (cid:0) (cid:0) (cid:0) r < n, i l 2 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

ừ ị ệ r = 0.

ị

ế ợ ỳ (cid:0) T đ nh nghĩa khái ni m chu k , ộ ướ ố ủ 2m – 1, (cid:0) (cid:0) T ừ Đ nh lý 11.4 c s c a l = h (cid:0) ớ 2i (cid:0) n là m t c s c a n là m t n (cid:0) ộ ướ ố ủ l, (cid:0) . ẽ n l n (cid:0) l

K t h p v i vô lý. n Đ nh lý 11.11

ị n (cid:0)

ề ồ ạ ứ ố ộ ả ườ i m t đa th c t i gi n b c ậ m trên tr ng m ≥ 1 đ u t n t Trang 56

GF(2).

ị

Đ nh lý

n Đ nh lý 11.12 ớ

ứ ố

ị ộ n V i m t đa th c t

i gi n ấ ỳ ả p(x) b t k có b c ậ m,

p(x) = b0 + b1x + … + bmxm

ự trong đó bm = 1, chúng ta luôn xây d ng đ ể ủ ứ ố ượ c m t tr ộ i thi u c a m t ph n t ộ ườ ầ ử



ườ GF(2m) trong đó p(x) là đa th c t ủ c a tr ng. (cid:0) (cid:0)

ể



(cid:0) (cid:0)



ộ

ự Đ xây d ng tr chúng ta cho ph n t m t ma trân

ườ GF(2m) ng ầ ử a là m(cid:0) m nh bênư

(cid:0) (cid:0)

0 

1 0 

0 

(cid:0) (cid:0) (cid:0) (cid:0)

(cid:0) (cid:0)



(cid:0) (cid:0)



b m

0 b 0

0 b 1

0 b 2

0 b 3

Trang 57

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

ị

Đ nh lý (tt)

ị ậ c ngộ và nhân ma tr n nh bình

n Trên ma tr n đ nh nghĩa phép ng, v i chú ý r ng vi c ậ ượ

ườ ằ

ậ ớ ủ ư ự ư ệ c ngộ ho c ặ nhân hai ph n t ầ ử ườ ệ ng c th c hi n nh trên tr

th trong 2 ô c a hai ma tr n đ GF(2).

n Chúng ta công nh n r ng ma tr n này có đa th c t

ậ ằ

ầ ử ứ ố c các ph n t ể i thi u là ạ i còn l

ậ ể ẫ ị ượ ừ p(x). T đây chúng ta có th d n ra đ ườ GF(2m) nh ờ Đ nh lý 11.5 ủ . c a tr

ầ ử ậ 0 chính là ma tr n 0 và ph n t 1 chính là ma

ng ầ ử n Chú ý, ph n t ị ơ ậ tr n đ n v . n Đ nh lý 11.13

ị n (cid:0)

ứ ố ườ ề m ≥ 2, các đa th c t ng GF(2) đ u là

ướ ố ủ c s c a (cid:0) ả 2 x ậ m trên tr i gi n b c (cid:0)m 11

t kê các đa th c t

Trang 58

ệ n Chúng ta có th quay tr v b ng li ả i gi n b c ả ứ ố i gi n ướ ố ủ x7 c s c a ậ 3 là

ả ở ề ả ể ứ ố ằ ể ể đ ki m tra r ng các đa th c t ậ 4 là ứ ố i gi n b c – 1, các đa th c t ướ ố ủ x15 – 1, … c s c a

ị

Đ nh lý (tt)

ứ ố ờ ồ i gi n, đ ng th i

ồ ạ ố ươ

ứ ả n Đa th c căn b n ả ứ M t đa th c căn b n là m t đa th c t i s nguyên d

ộ ng ả n < 2m – 1 sao cho xn + 1 chia

n Ví d , không t n t

ồ ạ ố ộ không t n t ế h t cho nó. ụ n < 15 sao cho xn + 1 i s nguyên d ng

ứ ả ươ 1 + x + x4 nên 1 + x + x4 là đa th c căn b n. ế chia h t cho

ố ư ả i gi n nh ng không căn

n Còn đa th c ứ 1 + x + x2 + x3 + x4 là t x5 + 1 chia h t cho nó.

ế ả b n vì

1, 2, 3 4, 5 6, 7, 8

1 + x 1 + x + x4 1 + x + x6

1 + x + x2 1 + x3 + 1 + x3 + x7

x5 1 + x2 + x3 + x4 + x8 1 + x + x3 1 + x2 + Trang 59

1 + x2 + 1 + x3 +

x3 x5

ị

Đ nh lý (tt)

ầ ử

ị n Cho a là m t ph n t

khác

n Đ nh lý 11.14 ộ f(x). N u ế f(x) là m t đa th c căn b n trên tr ể i thi u là

ủ 0 c a tr ộ ng ứ ườ

ậ ằ m thì a có chu k là ỳ

c s c a ầ ử ơ ở ủ GF(2m). ườ GF(2m) có đa th c ứ ả ng 2m – 1 và a là m t ộ l a 2

ố t GF(2) và có b c b ng ph n t ứ n Ch ng minh

ổ ề ế ợ ế ớ ỳ ủ a. Đ t ặ p(x) = xn + 1, thì p(a) = 0. p(x) chia h t cho f(x). K t h p đi u này v i

G i ọ n là chu k c a (cid:0) B đ 11.5 ủ ứ ề n = 2m – 1.

ợ

ườ GF(2m) ng ộ ứ ố ả (cid:0) ệ ị đ nh nghĩa c a khái ni m đa th c căn b n, ự i thi u là m t đa c s có đa th c t

Trang 60

ị n Đ nh lý này g i ý cho chúng ta cách xây d ng tr ự ể ầ ử ơ ở ộ d a trên m t ph n t ậ m. ả ứ th c căn b n b c

Tóm t

tắ

n Tóm t

tắ

(cid:0)m

(cid:0)

2 ườ GF(2m) thì a ng ộ ướ ố ủ 2m – 1. là m t c s c a ng

ứ ố ườ GF(2m) là các đa th c t i

ả

(cid:0) ầ ử ủ ộ n a là m t ph n t c a tr ộ ầ ử ỳ ủ n Chu k c a m t ph n t ể ủ ứ ố i thi u c a tr n Các đa th c t ướ ố ủ c s c a gi n và là (cid:0)m 2 x

11 H n n a b c c a chúng là

ơ ữ ậ ủ ướ ủ m. c c a

n S ph n t

ợ ố ầ ử ủ a, k c ể ả a, là

ầ ử liên h p c a nhau có cùng đa th c t

liên h p khác nhau c a ợ ủ ệ ứ ố

(cid:0)k

ứ ố ủ ằ

(cid:0)

n Các đa th c t

Trang 61

m. Các ph n t ơ ữ h n n a chúng là các nghi m c a đa th c t ậ ủ b c c a đa th c t khác nhau. Các ph n t ứ ố ướ ố ủ c s c a ứ ố ể i thi u, ể i thi u này và ợ ầ ử ố ể i thi u này b ng s các ph n t liên h p ợ ầ ử ỳ liên h p thì có cùng chu k . 11 x ướ ủ ậ k là ả c c a i gi n b c

ắ

Tóm t

t (tt)

ổ ợ ể i thi u b c ậ m thì các t h p

ầ ử a có đa th c t ứ ố GF(2)) tuy n tính (v i ớ bi (cid:0)

ộ n M t ph n t ế b01 + b1a + … + bk 1ak 1

ầ ử ủ ộ ẽ s sinh ra toàn b các ph n t c a tr ườ GF(2m) ng

n M t ph n t

ộ ứ ố

ầ ử a có đa th c t ừ ủ ể i thi u b c ẽ ậ m và cũng là đa th c ứ ộ ầ

Trang 62

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 ườ GF(2m). ả c a tr ng

Ví dụ

n Xây d ng tr n Chúng ta kí hi u ệ 0 là ma tr n ậ 0, kí hi u ệ 1 là ma tr n ậ đ n vơ

ự ườ GF(2m) v i ớ m = 4. ng

ị

ướ ậ (có kích th c là

(cid:0) (cid:0) 4(cid:0) 4). L y ph n t ấ 0 0 ầ ử a là ma tr n sau 0

(cid:0) (cid:0)

44T

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

(cid:0) (cid:0)

ứ ố Chúng ta có đa th c t i thi u c a

n Đây là m t đa th c căn b n b c

ả ứ ị

ậ ầ ử ủ GF(24) không tính ph n t ể ủ a là f(x) = 1 + x + x4 ậ 4. Vì v y theo ẽ ầ ử 0 s có d ng , Đ nh lý 11.14 ạ ai, i

c a ớ

ạ b0 + b1a + b2a2 + ộ 15 ph n t = 0, 1, …, 14 v i chú ý ị n Còn theo Đ nh lý 12.12 Trang 63 a0 = 1. ẽ chúng s có d ng b3a3 trong đó các bi = 0 ho c ặ 1.

Ví d (tt)ụ

ậ ư

ng ầ ử ể ể n V y có hai cách đ xây d ng tr n Các b ng sau đây bi u di n các ph n t ườ GF(24) nh trên. khác

ứ ủ ự ễ ạ ườ GF(24) theo các d ng: lũy th a c a 0 và khác 1 c a ủ ừ ủ a (ai), đa th c c a

ơ ạ ậ ả tr ng a, vect , d ng ma tr n.

a a2 a2 a3 a3 a4 1 + a a5 a + a2

0100 0010 0001 1100 0110

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 0 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 1 1 0 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

Trang 64

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 1 0 1 0 (cid:0) (cid:0) 0 1 1 0 0 0 1 1 1 1 0 1 1 1 0 0

Ví d (tt)ụ

a6 a2 + a3 a7 1 + a + a3 a8 1 + a2 a9 a + a3 a10 1 + a + a2

0011 1101 0101

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 1010 1 1 0 1 1110 1 0 1 0 0 0 1 1 1 1 0 1 1 0 1 0

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 1 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 1 1 1 1 1 1 1 0 1 0 1 0 0 1 0 1 1 1 1 0 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

Trang 65

(cid:0) (cid:0) (cid:0) (cid:0) 0 1 1 1 1 1 1 1 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 0 1 0 1 1 1 1 0 0 1 1 1

Ví d (tt)ụ

a11 a + a2 + a3 a13 1 + a2 + a3 a14 1 + a3

a12 1 + a + a2 + a3

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 1 1011 0 1 1 1 1001 0 0 1

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

1 0 0 1 1 0 0 0 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 0 1 1 0111 1 1 1 1 0 1 1 1 1 1 1 1 1111 1 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0 0 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0

1 0 a3, a6, a12, a9 a5, a10

a7, a14, a13, a11 ứ ố ợ liên h p

ầ ử i thi u c a các ph n t 3 ể ủ 5 15

a, a2, a4, a8 ỳ n Chu k , đa th c t 15 Trang 66 x 1 + x 1 + x + x4 1 + x3 + x4

1 + x + x2 + x3 + x4 1 + x + x2