Phân hoá của vành đa thức theo các phần tử liên hợp và ứng dụng trong lý thuyết mã

M• xyclic cục bộ (XCB) tuy còn non trẻ nhưng đ• tỏ ra có nhiều ưu điểm thoả m•n được yêu cầu thực tế của hệ thống truyền tin. Trong bài báo này, chúng tôi sẽ đề cập đến một cách phân hoạch mới trên vành đa thức chẵn Z2[x]/x2n+1 (ký hiệu là Z2n) đó là phân hoạch theo lớp các phần tử liên hợp và từ đây xây dựng m• XCB cụ thể trên phân hoạch này.
Nội dung trích xuất từ tài liệu:
Phân hoá của vành đa thức theo các phần tử liên hợp và ứng dụng trong lý thuyết mã LÜnh vùc C«ng nghÖ th«ng tin Ph©n ho¹ch cña vµnh ®a thøc theo c¸c phÇn tö liªn hîp vµ øng dông trong lý thuyÕt m· PGS.TS NguyÔn B×nh, KS. §Æng Hoµi B¾c Khoa Kü thuËt ®iÖn tö 1Tãm t¾t: M· xyclic côc bé (XCB) tuy cßn non trÎ nhng ®· tá ra cã nhiÒu u ®iÓmtho¶ m·n ®îc yªu cÇu thùc tÕ cña hÖ thèng truyÒn tin. Trong bµi b¸o nµy, chóngt«i sÏ ®Ò cËp ®Õn mét c¸ch ph©n ho¹ch míi trªn vµnh ®a thøc ch½n Z 2[x]/x 2n+1(ký hiÖu lµ Z 2n) ®ã lµ ph©n ho¹ch theo líp c¸c phÇn tö liªn hîp vµ tõ ®©y x©ydùng m· XCB cô thÓ trªn ph©n ho¹ch nµy.1. Ph©n ho¹ch cña vµnh ®a thøc Z 2n theo c¸c phÇn tö liªn hîp1.1 C¸c thÆng d bËc 2 vµ c¸c c¨n bËc 2 cña chóng.§Þnh nghÜa 1.1: §a thøc f(x) ®îc gäi lµ thÆng d bËc 2 (quadratic residue - QR)trong Z 2n nÕu tån t¹i ®a thøc g(x) sau: g2(x) ≡ f(x) mod x2n+1 (1.1)Nh vËy g(x) ∈ Z2n vµ ®îc gäi lµ c¨n bËc 2 (Square root - Sqr) cña f(x).NÕu g(x) = f ( x ) ®îc gäi lµ c¨n bËc 2 chÝnh cña f(x).Ch¼ng h¹n nÕu: f(x)= 1+ x 2 + x 4 th× c¨n bËc 2 chÝnh cña nã lµ: f ( x ) = 1+ x + x 2Bæ ®Ò 1.1:§a thøc f(x) n»m trong tËp c¸c thÆng d bËc 2 Q2n ( f(x) ∈ Q2n ) khi vµchØ khi f(x) chøa c¸c ®¬n thøc cã sè mò ch½n.Sè c¸c thÆng d bËc 2 trong Z2n ®îc x¸c ®Þnh nh sau: n  2n Q = ∑C i=0 i n 3 ( n −1) = Cn + Cn + Cn + ... + Cn + Cn = 2n 1 2 n (1.2)VÝ dô 1.1: Ta xÐt vµnh Z2n víi n=3 ta cã vµnh Z6 ( n = 3) TËp c¸c thÆng d bËc hai Q2n trong vµnh Z6 ®îc x¸c ®Þnh theo bæ ®Ò 2.1 nh sau: Q6 ={0, 1, x 2, x 4, 1+x 2, 1+x 4, x 2+x 4, 1+x 2+x 4} ( cã tÊt c¶ 23 - tøc 2n - phÇntö) Häc viÖn C«ng nghÖ BCVTHéi nghÞ Khoa häc lÇn thø 5Bæ ®Ò 1.2: C¸c c¨n bËc 2 cña mét thÆng d bËc 2 ®îc x¸c ®Þnh theo c«ng thøcsau:   sqr[f(x)] = g(x) = (1+xn )  ∑ x  + f ( x ) t  t∈U (1.3)Trong ®ã U lµ mét tËp gåm c¸c tæ hîp tuú ý c¸c gi¸ trÞ trong tËp s = {0, 1, 2,..., n-1}Do vËy lùc lîng cña U sÏ b»ng: = 2n -1 UVÝ dô 1.2: Trong tËp Q6 ë trªn ta xÐt mét QR bÊt kú ®Ó x¸c ®Þnh c¨n bËc 2,ch¼ng h¹n f(x)=x 2 ¸p dông c«ng thøc (1.3) tÝnh c¸c c¨n bËc hai ë trªn ta cã  t  sqr(x 2) = (1+x 3)  ∑ x  + x (víi f ( x ) =x)  t∈U  + khi U= {0, 1, 2} sqr(x 2) = (1+x 3)( 1+x+x 2) + x =1+x 2+x 3+x 4+x 5 + T¬ng tù ta cã: khi U = {0,1} sqr(x2) = (1+x3)( 1+x) + x = 1+x3+x4 Cø nh vËy ta sÏ t×m ®îc toµn bé 22n phÇn tö liªn hîp cña vµnh Z6.NhËn xÐt: - Trong vµnh Z2n cã 2n thÆng d bËc 2, mçi thÆng d bËc 2 cã 2n c¨n bËc 2, vËy cã tÊt c¶ 22n c¨n bËc 2 trong vµnh, c¸c c¨n bËc 2 nµy t¹o nªn toµn bé vµnh Z2n. - Ta sÏ gäi c¸c c¨n bËc 2 cña cïng mét thÆng d bËc 2 lµ c¸c phÇn tö liªn hîp (Conjugate Elements ) t ¬ng øng víi thÆng d ®ã ký hiÖu lµ CEs.1.2 Ph©n ho¹ch vµnh Z 2[x]/ x2n+1 theo c¸c phÇn tö liªn hîp §Ó kh¶o s¸t sù ph©n ho¹ch theo c¸c CE trªn vµnh Z 2[x]/x 2n+1, ta sÏ kh¶o s¸ttrªn vµnh cô thÓ Z6(n=3). TËp c¸c QR trong vµnh Z6 lµ: Q6 ={0, 1, x 2, x 4, 1+x 2,1+x 4, x 2+x 4, 1+x 2+x 4} Vµnh Z 6 Sqr (x 2) Sqr (x 4) Sqr (0) Sqr (1) Sqr (1+x 2+x 4) Sqr (1+x 4) Sqr (x 2+x 4) Sqr (1+x 2)Häc viÖn C«ng nghÖ BCVT LÜnh vùc C«ng nghÖ th«ng tin H×nh 1. Ph©n ho¹ch vµnh Z 6 theo líp ...