Khảo sát một số mã Xiclic vành đa thức X9+1

Chia sẻ: Quanghai Quanghai | Ngày: | Loại File: DOC | Số trang:10

Thêm vào BST

Báo xấu

193
lượt xem 29
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

: Các m• xyclic đ• có nhiều ứng dụng rất hiệu quả trong thực tiễn. Chúng được xây dựng trên các Ideal của vành đa thức, tuy nhiên số Ideal trên một vành đa thức ít nên số bộ tạo ra cũng hạn chế. Để mở rộng khả năng tạo thêm các m• trên một vành đa thức, bài báo đề cập đến phương pháp phân hoạch vành đa thức (cụ thể trên vành đa thức ), trên cơ sở đó khảo sát một số bộ m• xyclic không có trên vành X9+1 theo quan điểm xây dựng m•......

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Khảo sát một số mã Xiclic vành đa thức X9+1

LÜnh vùc C«ng nghÖ th«ng tin Kh¶o s¸t mét sè m· xiclic trªn vµnh ®a thøc x 9 + 1 PGS.TS. NguyÔn B×nh, KS. Ng« §øc ThiÖn Khoa Kü thuËt ®iÖn tö 1 Tãm t¾t: C¸c m· xyclic ®· cã nhiÒu øng dông rÊt hiÖu qu¶ trong thùc tiÔn. Chóng ®îc x©y dùng trªn c¸c Ideal cña vµnh ®a thøc, tuy nhiªn sè Ideal trªn mét vµnh ®a thøc Ýt nªn sè bé t¹o ra còng h¹n chÕ. §Ó më réng kh¶ n¨ng t¹o thªm c¸c m· trªn mét vµnh ®a thøc, bµi b¸o ®Ò cËp ®Õn ph¬ng ph¸p ph©n ho¹ch vµnh ®a thøc (cô thÓ trªn vµnh ®a thøc Z2 [ x ] x 9 + 1 ), trªn c¬ së ®ã kh¶o s¸t mét sè bé m· xyclic kh«ng cã trªn vµnh X 9+1 theo quan ®iÓm x©y dùng m· xyclic truyÒn thèng. 1. Mét s« kh¸i niÖm 1.1. Vµnh ®a thøc NÕu R lµ mét vµnh giao ho¸n th× vµnh ®a thøc R[x] lµ mét vµnh ®îc t¹o bëi tËp tÊt c¶ c¸c ®a thøc cña biÕn x cã c¸c hÖ sè trong R. Hai phÐp to¸n lµ phÐp céng vµ phÐp nh©n ®a thøc th«ng th êng víi sè häc c¸c hÖ sè ®îc thùc hiÖn trong vµnh R. Trong tr êng nhÞ ph©n, vµnh ®a thøc ®îc ký hiÖu: (f(x); f, •) = Z2[x]/ x n + 1 e(x) = 0 gäi lµ phÇn tö ®¬n vÞ, deg e(x) = 0 (bËc cña e(x) = 0) (f(x), +) lµ mét nhãm ®èi víi phÐp céng, tháa m·n c¸c tiªn ®Ò cña nhãm. (f(x), *) lµ nöa nhãm ®èi víi phÐp nh©n, kh«ng tån t¹i f(x), g(x) mµ f(x).g(x) = 0. CÊp cña mét ®a thøc, ký hiÖu ord a(x), lµ sè nguyªn d¬ng (m) nhá nhÊt sao cho: am (x) = e(x) mod (xn +1). Trong ®ã: e(x) lµ mét lòy ®¼ng nµo ®ã. 1.2. Nhãm nh©n TËp c¸c ®a thøc f(x) trong vµnh ®a thøc Z2[x]/ x n +1 víi mét phÐp to¸n nh©n ®a thøc t¹o nªn mét nhãm nh©n G. NÕu g(x), f(x) ∈ G th× g(x).f(x) = d(x) ∈ G. Trong nhãm nh©n tån t¹i phÇn tö ®¬n vÞ e(x) víi f(x).e(x) = f(x). Häc viÖn C«ng nghÖ BCVT
Héi nghÞ Khoa häc lÇn thø 5 C¸c phÇn tö ®¬n vÞ e(x) tháa m·n ®iÒu kiÖn: e(x) = e2(x) = e(x2) ®îc gäi lµ lòy ®¼ng. Trong mét vµnh Z2[x]/x n +1 cã thÓ tån t¹i nhiÒu lòy ®¼ng kh¸c nhau. a) Nhãm nh©n xyclic (CMG - Cyclic Multiplicate Groups) Nhãm nh©n xyclic trong vµnh ®a thøc lµ tËp hîp c¸c phÇn tö ®Òu b»ng lòy thõa cña mét phÇn tö gäi lµ phÇn tö sinh. Trong vµnh ®a thøc cã nhiÒu nhãm nh©n xyclic, sè nhãm nh©n b»ng sè c¸c lòy ®¼ng cã thÓ cã trong vµnh. A = {α, α2, α3,..} Trong ®ã: A lµ nhãm nh©n xyclic; α lµ phÇn tö sinh (®a thøc sinh), cÊp cña phÇn tö sinh lµ cÊp cña nhãm (cÊp cña nhãm lµ tæng sè c¸c phÇn tö cña nhãm). PhÇn tö ®¬n vÞ cña nhãm chÝnh lµ mét lòy ®¼ng e(x). b) Nhãm nh©n xyclic ®¬n vÞ Nhãm nh©n xyclic ®¬n vÞ lµ mét nhãm bao gåm mäi ®¬n thøc vµ cã cÊp lµ n. Ký hiÖu lµ I , hay nhãm nh©n xyclic ®¬n vÞ lµ nhãm nh©n xyclic víi phÇn tö sinh lµ x. I = {x, (x)2, (x)3, ..., (x)n-1, 1} c) Nhãm nh©n xyclic víi phÇn tö sinh a(x) Nhãm nh©n xyclic víi phÇn tö sinh lµ ®a thøc a(x) bao gåm c¸c phÇn tö lµ lòy thõa cña phÇn tö sinh vµ cã thÓ viÕt díi d¹ng: A = {a(x), (a(x))2, (a(x))3,...} 1.3. CÊp sè nh©n xyclic (CGP - Cyclic Geometic Progressions) trªn vµnh ®a thøc CÊp sè nh©n xyclic trªn vµnh ®a thøc lµ mét tËp hîp con cã d¹ng sau: A(a,q) = {a(x), a(x).q(x), a(x).q2(x), ..., a(x).qm -1(x)}. Trong ®ã: m lµ sè c¸c sè h¹ng cña cÊp sè nh©n; a(x) lµ sè h¹ng ®Çu cña cÊp sè nh©n; q(x) lµ c«ng béi; a(x).qm(x) ≡ a(x) mod x n + 1 Gi¸ trÞ cña m ®îc x¸c ®Þnh bëi cÊp cña nhãm nh©n xyclic. 2. CÊu t róc c¸c nhãm nh©n xyclic t rong vµnh ®a thøc Z 2[x] /x9 + 1 2.1. CÊu tróc c¸c nhãm nh©n Víi vµnh Z2[x]/ x 9 + 1, ta cã n = 9 (lµ sè lÎ). + Khai triÓn nhÞ thøc: x 9 + 1 = (1 + x)(1 + x + x 2)(1 + x 3 + x 6). Vµnh ®a thøc nµy cã cã 29 - 1 = 511 phÇn tö kh¸c 0. Trong ®ã cã: 256 phÇn tö cã träng sè lÎ. Häc viÖn C«ng nghÖ BCVT
LÜnh vùc C«ng nghÖ th«ng tin 255 phÇn tö cã träng sè ch½n. + CÊp cùc ®¹i cña ®a thøc a(x) ®îc x¸c ®Þnh nh sau: Max ord(a(x)) = 2m -1 = 26 - 1 = 63. ë ®©y m còng chÝnh b»ng max m s = 6, hay cÊp lín nhÊt cña ®a thøc bÊt kh¶ quy trong khai triÓn nhÞ thøc x 9 +1. + Ph©n tÝch max ord(a(x)) ra thõa sè nguyªn tè ®Ó x¸c ®Þnh c¸c íc cña nã: Max ord(a(x)) = 63 = 3.3.7. + CÊp c¸c phÇn tö trong vµnh lµ c¸c íc sè cña max ord(a(x)), t ¬ng øng c¸c nhãm nh©n trong vµnh cã c¸c cÊp lµ: 1, 3, 7, 9, 21, 63. + X¸c ®Þnh c¸c chu tr×nh Cs. C¸c chu tr×nh Cs ®îc x¸c ®Þnh nh sau: { } Cs = s, s.2, s.22 ,..., s.2ms −1 trong ®ã s.2ms −1 ≡ s mod n C0 = {0} → |C 0| = m 0 = 1 C1 = {1, 2, 4, 8, 7, 5} → |C 1| = m 1 = 6 C3 = {3, 6} → |C 3| = m 3 = 2 §a thøc e(x) lµ mét lòy ®¼ng khi vµ chØ khi tËp c¸c hÖ sè kh¸c kh«ng cña nã lµ hîp mét sè c¸c chu tr×nh Cs nµo ®ã. C¸c lòy ®¼ng chÝnh lµ c¸c phÇn tö ®¬n vÞ cña c¸c nhãm nh©n xyclic trong vµnh ®a thøc. Ta t×m ®îc c¸c lòy ®½ng nh sau: B¶ng 1: C¸c lòy ®¼ng cña vµnh ®a thøc Z 2[x]/ x 9 + 1 D¹ng sè mò C¸c chu tr×nh C¸c lòy ®¼ng cña ®a thøc t ¬ng øng e1(x) = 1 + x + x 2 + x 4 + x 5 + x 7 + x 8 (0124578) C0 ∪ C1 e2(x) = 1 + x 3 + x 6 (036) C0 ∪ C3 e3(x) = e0(x) = 1 + x + x 2 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 (012345678) C0 ∪ C1 ∪ C3 e4(x) = 1 (0) C0 e5(x) = x 3 + x 6 (36) C3 e6(x) = x + x 2 + x 4 + x 5 + x 7 + x 8 (124578) C1 e7(x) = x + x 2 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 (12345678) C1 ∪ C3 256 phÇn tö cã träng sè lÎ bao gåm: Häc viÖn C«ng nghÖ BCVT
Héi nghÞ Khoa häc lÇn thø 5 1 nhãm nh©n cÊp 63 víi phÇn tö sinh a1(x) = (012), víi lòy ®¼ng e1(x) = (0124578). 1 nhãm nh©n cÊp 3 víi phÇn tö sinh a2(x) = (147), víi lòy ®¼ng e2(x) = (036). 1 nhãm nh©n cÊp 1 víi phÇn tö sinh a3(x) = e3(x) = (012345678). 3 nhãm nh©n cÊp 63 víi phÇn tö sinh a4(x) = (014), a5(x) = (016), a6(x) = (02357) víi lòy ®¼ng e4(x) = (0). 1 nhãm nh©n cÊp 21 víi phÇn tö sinh b1(x) = (12345), víi lòy ®¼ng e4(x) = (0). 3 nhãm nh©n cÊp 21 víi phÇn tö sinh a7(x) = (124), a8(x) = (245), a9(x) = (128) víi lòy ®¼ng e4(x) = (0). Mét nhãm nh©n cÊp 7 víi phÇn tö sÝnh b2(x) = (12345) víi lòy ®¼ng e4(x) = (0). 2.2. Ph ¬ng ph¸p ph©n ho¹ch vµnh ®a thøc thµnh nhãm nh©n xyclic C¸c bíc ph©n ho¹ch vµnh ®a thøc ®Ó x©y dùng c¸c nhãm nh©n xyclic cã thÓ kh¸i qu¸t nh sau: - T×m cÊp cùc ®¹i cña nhãm nh©n xyclic trong vµnh. - T×m phÇn tö sinh cã cÊp lín nhÊt. Do vµnh ®a thøc cã cÊu tróc ®èi xøng, mét nöa vµnh gåm c¸c phÇn tö cã träng sè lÎ, mét nöa vµnh gåm c¸c phÇn tö cã träng sè ch½n. H¬n n÷a do vµnh ®èi xøng nªn khi biÕt nöa vµnh cã thÓ suy ra nöa vµnh kia. V× vËy tr íc tiªn ta ®i x¸c ®Þnh c¸c phÇn tö cã träng sè lÓ. Trong c¸c phÇn tö cã träng sè lÎ x¸c ®Þnh c¸c phÇn tö sinh cã cÊp lín nhÊt. Sau ®ã x©y dùng tÊt c¶ c¸c nhãm nh©n chøa c¸c phÇn tö cã träng sè lÎ. §Ó x©y dùng ®îc tÊt c¶ c¸c nhãm nh©n ta ph¶i thùc hiÖn c¸c bíc: o X¸c ®Þnh tÊt c¶ c¸c ®a thøc lòy ®¼ng trong vµnh, trªn c¬ së ph©n tÝch c¸c chu tr×nh. o Chän c¸c ®a thøc lòy ®¼ng cã träng sè lÎ ®Ó x©y dùng c¸c nhãm nh©n chøa chóng. - X©y dùng tÊt c¶ c¸c nhãm nh©n xyclic cã thÓ cã cña vµnh. Tïy theo tõng lòy ®¼ng mµ mçi lòy ®¼ng cã thÓ tham gia trong nhiÒu nhãm nh©n. - LÊy ®èi xøng tÊt c¶ c¸c nhãm nh©n cã chøa c¸c phÇn tö cã träng sè lÎ sÏ t¹o ®îc tÊt c¶ c¸c nhãm nh©n cã chøa c¸c phÇn tö cã träng sè ch½n. 3. Kh ¶o s¸t mét sè m· xyclic vµ xyclic côc bé t rªn vµnh ®a thøc X 9 + 1 3.1. Kh¸i niÖm m· xyclic côc bé (XCB) Häc viÖn C«ng nghÖ BCVT
LÜnh vùc C«ng nghÖ th«ng tin M· xyclic côc bé lµ m· hÖ thèng tuyÕn tÝnh (n, k) trong ®ã: k dÊu th«ng tin ®îc chän lµ k ®¬n thøc cã d¹ng x ( i = 0,1, 2,..., k − 1) vµ lµ nhãm i nh©n xyclic cÊp k cña vµnh Z 2 [ x ] / ( x + 1) . n r = n − k dÊu kiÓm tra ®îc chän lµ mét tËp con kh«ng trèng tïy ý nµo ®ã c¸c líp kÒ cña nhãm nh©n nµy. TËp c¸c tr ëng líp kÒ t¹o m· sÏ cho ta m« t¶ ®Çy ®ñ cña m· xyclic côc bé. 3.2. Mèi quan hÖ gi÷a m· xyclic vµ xyclic côc bé Theo quan ®iÓm x©y dùng m· xyclic th«ng th êng: m· xyclic lµ mét Ideal cña vµnh ®a thøc; trong ®ã mçi tõ m· lµ mét phÇn tö cña Ideal ®ã trªn vµnh ®a thøc. Theo quan ®iÓm x©y dùng m· XCB mèi dÊu m· lµ mét phÇn tö cña Ideal; toµn bé tõ m· lµ mét bé phËn cña vµnh gåm n phÇn tö x¸c ®Þnh cña Ideal. Nh vËy, ta hoµn toµn cã thÓ dïng lý thuyÕt x©y dùng c¸c ®a thøc sinh cña m· xyclic ®Ó t¹o c¸c tr ëng líp kÒ cho c¸c m· XCB. Víi quan ®iÓm ®ã: líp kÒ ®îc x©y dùng theo c¸ch sau ®©y sÏ t¹o nªn mét m· xyclic: M· XCB ®îc x©y dùng tõ: + Tr ëng líp kÒ lµ mét ®a thøc sinh g(x) tháa m·n: − §a thøc sinh lµ íc cña x + 1; g ( x ) x + 1 . n n − BËc cña ®a thøc sinh b»ng r víi r = n – k. − Sö dông r dÊu th«ng tin gi¶ khi t¹o líp kÒ nµy; tøc lµ cho tr íc: x 0 = x1 = x 2 = ... = x n −1 = 0 . Trªn c¬ së ph©n tÝch nh vËy th× m· xyclic lµ mét líp kÒ ®Æc biÖt cña m· XCB. Hay m· xyclic lµ mét d¹ng ®Æc biÖt cña m· XCB. 3.3. Kh¶o s¸t mét sè m· xyclic vµ xyclic côc bé trªn vµnh ®a thøc x9 + 1 a) Kh¶o s¸t m· xyclic (n, k) víi k = m. Trong mét vµnh ®a thøc lu«n tån t¹i m· xyclic (m, m) cã d 0 = 1, m· nµy ®îc x©y dùng tõ nhãm nh©n ®¬n vÞ. I = x , i = 1, m − 1 i { } M· nµy kh«ng cã kh¶ n¨ng ph¸t hiÖn vµ söa sai. Do sè dÊu th«ng tin k = m, nªn ®Ó t¹o c¸c m· cã kh¶ n¨ng ph¸t hiÖn vµ söa sai x©y dùng trªn c¸c nhãm nh©n xyclic th× yªu cÇu ph¶i tháa m·n ®iÒu kiÖn n > m . Hay nãi c¸ch kh¸c lµ cÊp cña nhãm nh©n Häc viÖn C«ng nghÖ BCVT
Héi nghÞ Khoa häc lÇn thø 5 xyclic t¹o m· ph¶i lín h¬n vµ b»ng béi cña m, nhãm nh©n ®¬n vÞ I ph¶i lµ nhãm nh©n con cña nhãm nh©n xyclic t¹o m·. Nhãm nh©n xyclic t¹o m· (n, m) ph¶i tháa m·n 2 ®iÒu kiÖn: − Nhãm nh©n xyclic ®¬n vÞ cã cÊp m ph¶i lµ mét nhãm con cña nhãm nh©n xyclic cÊp n ( n Mm hoÆ m n ) . c − CÊp cña nhãm nh©n xyclic t¹o m· (n, m) ph¶i lµ íc nµo ®ã cña cÊp sè lín nhÊt c¸c phÇn tö trong vµnh: n max ord a( x ) . Trong vµnh Z2[x]/ x 9 + 1, ta cã m = 9. x9 + 1 = ( 1 + x ) ( 1 + x + x 2 ) ( 1 + x3 + x6 ) . Ta cã max ord a(x) = 26 - 1 = 63 = 1.3.3.7. Do ®ã, trong vµnh nµy tån t¹i c¸c nhãm nh©n cã cÊp: 1, 3, 7, 9, 21, 63. Nh ng chØ cã c¸c nhãm nh©n cã cÊp 9 vµ 63 míi t¹o ®îc m· xyclic. M· xyclic ®îc x©y dùng trªn c¸c nhãm nh©n cã cÊp 9 vµ 63 lµ 2 lo¹i m· xyclic (9, 9) vµ (63, 9). { } { M· (9, 9) ⇔ I = x , i = 0,8 , m· (63, 9) ⇔ A = a ( x ) , i = 0, 62 . i i } * M· xyclic (63, 9) x©y dùng trªn nhãm nh©n cÊp 63 XÐt ®a thøc sinh a = (1 + x 2 + x 3 + x 5 + x 7), ®a thøc nµy cã cÊp 63. CÊu tróc cña nhãm nh©n lµ A = {ai = (1 + x 2 + x 3 + x 5 + x 7); i = 0, 1, 2,…, 62}. §¸nh gi¸: Sè tæng kiÓm tra (TKT) tù trùc giao cña m· nµy: J = 17, do ®ã kho¶ng c¸ch tèi thiÓu d0 = 18. k −1 d  Theo giíi h¹n díi cña ®é dµi tõ m· (giíi h¹n Griesmer): n ≥ ∑  0j  j =0  2  8  18  ta cã: n ≥ ∑  j  = 18 + 9 + 5 + 3 + 2 + 1 + 1 + 1 + 1 = 41 . j =0  2  Víi m· nµy cã ®é dµi tõ m· lµ n = 63 > 41 ⇒ m· kh«ng tèi u. b) Kh¶o s¸t c¸c m· xyclic (n, k) víi k < m. * M· xyclic (63, 7). Chän nhãm nh©n xyclic theo modulo h ( x ) = 1 + x + x + x + x + x víi phÇn tö sinh 3 4 6 7 cña nhãm nh©n lµ: α = ( 1 + x + x ) ↔ ( 014 ) cã cÊp lµ 63, lµm m· xyclic (63,7). 4 Nhãm nh©n nµy cã d¹ng nh sau: Häc viÖn C«ng nghÖ BCVT
LÜnh vùc C«ng nghÖ th«ng tin A = { α i mod h ( x ) , i = 0,1, 2,..., 62} = { ( 014) mod h ( x ) , i = 0,1, 2,..., 62} i Do m· nµy lµ m· xyclic cã kh¶ n¨ng trùc giao, cho nªn ph¶i gi¶i m· 2 cÊp. ë cÊp ngìng thø nhÊt gi¶i m· ra c¸c cÆp dÊu th«ng tin, sau ®ã qua bíc gi¶i m· cÊp ng- ìng thø hai míi gi¶i m· ®îc toµn bé c¸c dÊu th«ng tin. §¸nh gi¸: Sè TKT tù trùc giao cña m· nµy lµ: J = 30, do ®ã kho¶ng c¸ch tèi thiÓu d 0 = 31.  30 + 1  CÊp ngìng gi¶i m· lµ: M =  = 16 .  2   Theo giíi h¹n Griesmer: m −1  d  6  31  n ≥ ∑  0  = ∑  i  = 31 + 16 + 8 + 4 + 2 + 1 + 1 = 63 ⇒ M· nµy lµ m· tèi u. i i =0  2  i =0  2  c) Kh¶o s¸t m· xyclic côc bé. * M· XCB (27, 9) M· XCB (27 9) ®îc x©y dùng tõ 3 cÊp sè nh©n (CGP) xyclic lÊy trong ph©n ho¹ch vµnh ®a thøc Z 2 [ x ] / x + 1 thµnh c¸c CGP cÊp 9. CGP1 chÝnh lµ nhãm nh©n 9 xyclic ®¬n vÞ (lµ ®a thøc th«ng tin). Chän CGP2 (tr ëng líp kÒ lµ (7)) vµ CGP3 (tr ëng líp lµ (11)) lµm c¸c dÊu kiÓm tra. Do CGP2 vµ CGP3 lµ 2 líp kÒ lÎ liªn tiÕp, cho nªn m· nµy sÏ lµ m· XCB cã kh¶ n¨ng trùc giao. CÊu tróc tõ m· XCB (27,9) nµy nh sau: (c¸c dÊu m· biÓu diÔn ë d¹ng thËp ph©n). 1 2 4 8 16 32 64 12 25 7 14 28 56 11 22 44 38 25 11 22 44 88 17 35 19 38 26 8 6 2 4 8 5 9 6 2 3 6 1 NÕu biÓu diÓn m· XCB nµy theo tr ëng líp kÒ th× cã d¹ng {1, 7, 11}. Sè TKT cã kh¶ n¨ng trùc giao J = 6 ⇒ d0 = 7. Theo giíi h¹n Griesmer th× m· nµy còng kh«ng tèi u: 3.4. Ph ¬ng ph¸p gi¶i m· ngìng Cã c¸c phu¬ng ph¸p gi¶i m· nguìng sö dông cho viÖc gi¶i m· XCB: + Gi¶i m· nguìng theo ®a sè (GM§S). + Gi¶i m· nguìng ®¹i sè kh¸c: gi¶i m· nguìng trªn ®a sè 1 biÓu quyÕt (GM§S + 1), gi¶i m· nguìng trªn ®a sè 2 biÓu quyÕt (GM§S +2). * Ph ¬ng ph¸p gi¶i m· ngìng theo ®a sè (GM§S) Häc viÖn C«ng nghÖ BCVT
Héi nghÞ Khoa häc lÇn thø 5 Gi¶ sö ta xÐt mét bé m· tù trùc giao nµo ®ã, víi bé m· nµy ta cã thÓ x©y dùng ®îc J tæng kiÓm tra trùc giao cho mét dÊu m· nµo ®ã. {S m , m = 1, J } J  J + 1 NÕu ∑S m =1 m ≥  2   , trong ®ã  x  lµ sè nguyªn nhá nhÊt lín h¬n hoÆc b»ng x.   Th× coi ei = 1 cã sai ë dÊu thø i, ngîc l¹i ei = 0: dÊu thø i thu ®óng. Mçi tæng kiÓm tra (TKT) trong hÖ J TKT nµy cho phÐp ®a ra c¸c dÊu ai ë d¹ng tæ hîp tuyÕn tÝnh cña c¸c dÊu kh¸c mµ nã kh«ng n»m trong mét TKT. V× vËy cã 2t TKT (2t = d0 –1 = J ) ®Ó gi¶i m· ®óng c¸c dÊu ai theo biÓu quyÕt ®a sè. Do c¸c TKT ph¶i tháa m·n víi bÊt kú tõ m· nµo th× tÝnh chÊt tuÇn hoµn cña bé m· míi cã hiÖu qu¶ ®Ó gi¶i m· c¸c dÊu tiÕp theo. Do vËy ta dÞch chuyÓn tuÇn hoµn tõ m· vµ l¹i ¸p dông biÓu quyÕt theo ®a sè. Cø nh vËy sÏ thùc hiÖn gi¶i m· cho tÊt c¶ c¸c dÊu m·. Nh vËy víi m· xyclic tù trùc giao th× ph¬ng ph¸p gi¶i m· ngìng ®¬n gi¶n h¬n nhiÒu so víi c¸c ph¬ng ph¸p gi¶i m· kh¸c vÒ thiÕt bÞ gi¶i m· víi bé m· cã cïng chiÒu dµi. ThiÕt bÞ gi¶i m· chØ gåm bé ghi, bé céng vµ thiÕt bÞ ngìng theo ®a sè. ChÝnh cã u ®iÓm nµy nªn viÖc thùc hiÖn kü thuËt sÏ ®¬n gi¶n. §èi víi c¸c m· cã kh¶ n¨ng trùc giao, ta cã thÓ thiÕt lËp ®îc hÖ TKT cã kh¶ n¨ng trùc giao. Mét hÖ TKT cã kh¶ n¨ng trùc giao nÕu tån t¹i mét tæ hîp tuyÕn tÝnh c¸c dÊu m·: M = xi1 + xi 2 + ... + xim tháa m·n ®iÒu kiÖn sau: + Tæ hîp tuyÕn tÝnh c¸c dÊu m· M cã mÆt trong mäi TKT. + C¸c dÊu cßn l¹i: x j ∉ M chØ n»m ë nhiÒu nhÊt mét TKT. Trªn c¬ së ®ã ta cã thÓ coi tËp M ®ãng vai trß nh mét dÊu m· x trong hÖ TKT trùc giao. Theo nguyªn t¾c gi¶i m· theo ®a sè, ta cã thÓ gi¶i m· cho tËp M hay cã thÓ nãi ®©y lµ hÖ TKT trùc giao víi tËp M. Th«ng th êng tËp M lµ mét cÆp dÊu m·. 4. Ch¬ng t r×nh m« pháng m· hãa vµ gi ¶ i m· mét sè m· xyclic vµ xyclic côc bé trªn vµnh ®a thøc X 9 + 1 Ch¬ng tr×nh m« pháng ®îc viÕt trªn phÇn mÒm MATLAB, víi u ®iÓm: − Ch¬ng tr×nh ®¬n gi¶n, tèc ®é tÝnh to¸n nhanh. − Cã thÓ m« pháng thªm c¸c bé m· kh¸c dùa trªn c¸c hµm mµ ch¬ng tr×nh m« pháng ®· lËp. Häc viÖn C«ng nghÖ BCVT
LÜnh vùc C«ng nghÖ th«ng tin Giao diÖn cña ch¬ng tr×nh m« pháng m· hãa vµ gi¶i m·. 4.1. M· cã ®é dµi 63 4.2. M· cã ®é dµi 27 KÕt luËn M· xyclic lµ mét trong c¸c m· dÔ thùc hiÖn vµ ®· ®îc øng dông nhiÒu trong thùc tÕ. ¦u ®iÓm cña m· xyclic ®ã lµ: lµ lo¹i m· cã cÊu tróc ®¹i sè t êng tËn, cã nhiÒu ph¬ng ph¸p gi¶i m· hiÖu qu¶, lËp m· vµ gi¶i m· ®¬n gi¶n. §Ó x©y dùng m· xyclic ngêi ta tiÕn hµnh ph©n ho¹ch vµnh ®a thøc thµnh c¸c Ideal, Ideal thùc chÊt lµ mét nhãm con cña nhãm céng trong vµnh. Tuy nhiªn, sè Ideal trong mét vµnh ®a thøc Ýt nªn kh¶ n¨ng t¹o c¸c bé m· xyclic còng bÞ h¹n chÕ. §Ó më réng kh¶ n¨ng t¹o m· cã thÓ x©y dùng c¸c m· xyclic côc bé trªn vµnh ®a thøc. B»ng c¸ch ph©n ho¹ch vµnh ®a thøc thµnh c¸c nhãm nh©n xyclic hoÆc c¸c cÊp sè nh©n xyclic, trªn c¬ së c¸c nhãm nh©n vµ cÊp sè nh©n xyclic nµy x©y dùng c¸c m· xyclic vµ xyclic côc bé. Kh¸c víi c¸c m· xyclic th«ng th êng (mçi tõ m· lµ mét phÇn tö cã cÊu tróc ®¹i sè), víi m· xyclic côc bé mçi dÊu m· trong mét tõ m· Häc viÖn C«ng nghÖ BCVT
Héi nghÞ Khoa häc lÇn thø 5 lµ mét phÇn tö cã cÊu tróc ®¹i sè. Do ®ã m· xyclic côc bé cã cÊu tróc ®¹i sè tinh tÕ h¬n vµ còng v× thÕ mµ kh¶ n¨ng söa sai cña nã tèt h¬n. Tµi liÖu tham kh ¶o [1] F.J. Mac Williams, N.J.A. Sloane: The theory of error-correcting codes. North- Holland Publisher Com. 1977. [2] A.J. Menezes, P.C. Van Oorchot, S.A. Vanstone: Handbook of Applied Cryptography. CRC Press 1998. [3] Ass.Prof. NguyÔn B×nh, NguyÔn Quèc H ng: Circuland Crypto-System based on polynominal ring with two cycloctomic cosets. [4] PGS. TS. NguyÔn B×nh, ThS. Vò ViÖt, KS. TrÇn §øc Sù: C¸c vµnh ®a thøc cã hai líp kÒ xyclic trong lý thuyÕt m· hãa. [6] Vò ViÖt: Ph©n ho¹ch vµnh ®a thøc. Chuyªn ®Ò tiÕn sÜ, 2001 [7] Nguyen Binh. Tran Duc Su, Pham Viet Trung. "Decomposition of polynomial ring according to the classes of conjugate elements". ATC - 26. Hanoi, 10.2001. [8] Nguyen Binh, Vu Viet, Pham Viet Trung. "Decomposition of polynomial ring and coding with random clock". CAFEO 2000. Hanoi, 22-24 Nov, 2000. Häc viÖn C«ng nghÖ BCVT

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn