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ö 1
Tãm t¾t: M· xyclic côc bé (XCB) tuy cßn non trÎ nhng ®· 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]/x 2n+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.
1. Ph©n ho¹ch cña vµnh ®a thøc Z2n theo c¸c phÇn tö liªn hîp
1.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 Z2n 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) =
)x(f
®îc gäi lµ c¨n bËc 2 chÝnh cña f(x).
Ch¼ng h¹n nÕu: f(x)= 1+ x2 + x4 th× c¨n bËc 2 chÝnh cña nã lµ:
)x(f
= 1+ x + x2
Bæ ®Ò 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:
Q2n=
∑
=
n
0i
i
n
C
=
1 2 3 ( 1)
...
n n
n n n n n
C C C C C
−
+ + + + +
= 2n (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, x2, x4, 1+x2, 1+x4, x2+x4, 1+x2+x4} ( cã tÊt c¶ 23 - tøc 2n - phÇn
tö)
Häc viÖn C«ng nghÖ BCVT
Héi nghÞ Khoa häc lÇn thø 5
Bæ ®Ò 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øc
sau:
sqr[f(x)] = g(x) = (1+xn)
)x(fx
Ut
t
+
∑
∈
(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:U = 2n -1
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)=x2
¸p dông c«ng thøc (1.3) tÝnh c¸c c¨n bËc hai ë trªn ta cã
sqr(x2) = (1+x3)
xx
Ut
t+
∑
∈
(víi
)x(f
=x)
+ khi U= {0, 1, 2} sqr(x2) = (1+x3)( 1+x+x2) + x =
1+x2+x3+x4+x5
+ 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 Z2[x]/ x2n+1 theo c¸c phÇn tö liªn hîp
§Ó kho s¸t sù ph©n ho¹ch theo c¸c CE trªn vµnh Z2[x]/x2n+1, ta sÏ kho s¸t
trªn vµnh cô thÓ Z6(n=3). TËp c¸c QR trong vµnh Z6 lµ: Q6 ={0, 1, x2, x4, 1+x2,
1+x4, x2+x4, 1+x2+x4}
Häc viÖn C«ng nghÖ BCVT
Sqr(1)
Sqr(x2+x4)
Sqr(0)
Sqr(x4)
Sqr(x2)
Sqr(1+x2+x4)
Vµnh Z
LÜnh vùc C«ng nghÖ th«ng tin
H×nh 1. Ph©n ho¹ch vµnh Z6 theo líp c¸c phÇn tö liªn hîp
Ta thÊy r»ng, ®èi víi phÐp céng
⊕
c¸c CEs ë h×nh 1 sÏ tho m·n b¶ng 1
nh sau:
⊕
Sqr(1) Sqr(x2) Sqr(x4) Sqr(1+x2) Sqr(1+x4) Sqr(x2+x4) Sqr(1+x2+x
4)
Sqr(0)
Sqr(1) Sqr(0) Sqr(1+x2) Sqr(1+x4) Sqr(x2) Sqr(x4) Sqr(1+x2+x
4)
Sqr(x2+x4) Sqr(1)
Sqr(x2)Sqr(1+x2) Sqr(0) Sqr(x2+x4) Sqr(1) Sqr(1+x2+x
4)
Sqr(x4) Sqr(1+x4) Sqr(x2)
Sqrh(x4)Sqr(1+x4) Sqr(x2+x4) Sqr(0) Sqr(1+x2+x
4)
Sqr(1) Sqr(x2) Sqr(1+x2) Sqr(x4)
Sqr(1+x2)Sqr(x2) Sqr(1) Sqr(1+x2+x
4)
Sqr(0) Sqr(x2+x4) Sqr(1+x4) Sqr(x4) Sqr(1+x2)
Sqr(1+x4)Sqr(x4) Sqr(1+x2+x
4)
Sqr(1) Sqr(x2+x4) Sqr(0) Sqr(1+x2) Sqr(x2) Sqr(1+x4)
Sqr(x2+x4)Sqr(1+x2+x
4)
Sqr(x4) Sqr(x2) Sqr(1+x4) Sqr(1+x2) Sqr(0) Sqr(1) Sqr(x2+x4)
Sqr(1+x2+x
4)
Sqr(x2+x4) Sqr(1+x4) Sqr(1+x2) Sqr(x4) Sqr(x2) Sqr(1) Sqr(0) Sqr(1+x2+x
4)
Sqr(0) Sqr(1) Sqr(x2) Sqr(x4) Sqr(1+x2) Sqr(1+x4) Sqr(x2+x4) Sqr(1+x2+x4
)
Sqr(0)
Bng 1. PhÐp céng modulo víi c¸c phÇn tö liªn hîp trong vµnh Z6
Ta kiÓm tra mét phÐp céng modulo trong b¶ng trªn ch¼ng h¹n: Sqr(1)+Sqr(x4) =
Sqr(1+x4)
Ta cã: 1+x+x4∈sqr(1) x5∈ Sqr(x4)
1+x+x4
⊕
x5 = 1+x+x4+x5 ∈ Sqr(1+x4) ( tho m·n)
KiÓm tra víi c¸c tæng kh¸c trong b¶ng 1, chóng ta thÊy chóng ®Òu tháa
m·n do vËy râ rµng lµ líp c¸c phÇn tö liªn hîp t¹o nªn mét nhãm Aben céng tÝnh.
+ §èi víi phÐp nh©n, líp c¸c phÇn tö liªn hîp trong vµnh Z6 còng tho m·n
b¶ng sau:
⊗Sqr(1) Sqr(x2) Sqr(x4) Sqr(1+x
2)
Sqr(1+x
4)
Sqr(x 2+x
4)
Sqr(1+x2+x
4)
Sqr(0
)
Sqr(1) Sqr(1) Sqr(x2) Sqr(x4) Sqr(1+x2
)
Sqr(1+x4
)
Sqr(x2+x4
)
Sqr(1+x2+x4
)
Sqr(0
)
Sqr(x2)Sqr(x2) Sqr(x4) Sqr(1) Sqr(x2+x
4)
Sqr(1+x2
)
Sqr(1+x4) Sqr(1+x2+x4
)
Sqr(0
)
Sqrh(x4)Sqr(x4) Sqr(0) Sqr(x2) Sqr(1+x4
)
Sqr(x2+x
4)
Sqr(1+x2) Sqr(1+x2+x4
)
Sqr(0
)
Sqr(1+x2)Sqr(1+x2) Sqr(x2+x4) Sqr(1+x4) Sqr(1+x4
)
Sqr(x2+x
4)
Sqr(1+x2) Sqr(0) Sqr(0
)
Sqr(1+x4)Sqr(1+x4) Sqr(1+x2) Sqr(x2+x4) Sqr(x2+x
4)
Sqr(1+x2
)
Sqr(1+x4) Sqr(0) Sqr(0
)
Häc viÖn C«ng nghÖ BCVT
Héi nghÞ Khoa häc lÇn thø 5
Sqr(x2+x4)Sqr(x2+x4) Sqr(x2+x4) Sqr(1+x2) Sqr(1+x2
)
Sqr(1+x4
)
Sqr(x2+x4
)
Sqr(0) Sqr(0
)
Sqr(1+x2+x
4)
Sqr(1+x2+x
4)
Sqr(1+x2+x
4)
Sqr(1+x2+x
4)
Sqr(0) Sqr(0) Sqr(0) Sqr(1+x2+x4
)
Sqr(0
)
Sqr(0) Sqr(0) Sqr(0) Sqr(0) Sqr(0) Sqr(0) Sqr(0) Sqr(0) 0
Bng 2. PhÐp nh©n modulo víi c¸c phÇn tö liªn hîp trong vµnh Z6
Ta kiÓm tra c¸c kÕt qu trong b¶ng trªn, ch¼ng h¹n nh:
Sqr(1+x2)x Sqr(x4) = Sqr(1+x4) (lu ý Sqr(1+x4) = Sqr((1+x2) x x4))
XÐt: (x3+x4) ∈ Sqr(1+x2) vµ (1+x2+x3) ∈ Sqr(1+x+x2)
Ta cã: (x3+x4)x(1+x2+x3) = (x3+x4+x6+x5+x6+x7)mod(x6+1) = x+x3+x4+x5 ∈
Sqr(1+x4)
Mét c¸ch t¬ng tù nh trªn ta cã thÓ kiÓm tra toµn bé c¸c phÐp nh©n gi÷a
c¸c cÆp c¸c phÇn tö liªn hîp nh trong b¶ng 2.
Tõ kÕt qu ë b¶ng 2 ta thÊy r»ng, c¸c phÇn tö liªn hîp trong vµnh Z6 t¹o
nªn mét nhãm theo phÐp nh©n víi phÇn tö ®¬n vÞ lµ Sqr(1), nhng lu ý sÏ cã tr -
êng hîp hai phÇn tö kh¸c 0 nhng khi thùc hiÖn phÐp nh©n theo mod (x6+1), ta
l¹i nhËn ®îc kÕt qu l¹i b»ng 0.
Ta cã thÓ lÊy vÝ dô :
(x+x3) ∈ Sqr(1+x2) (1+x2+x4) ∈ Sqr(1+x2+x4)
Khi thùc hiÖn phÐp nh©n: (x+x3) x (1+x2+x4) = (x+x3+x3+x5+x5+x7) mod (x6+1) =
x+x = 0.
VËy, c¸c phÇn tö liªn hîp cña c¸c thÆng d bËc 2 trong vµnh Z6 t¹o nªn mét nöa
nhãm nh©n.
NhËn xÐt:
- Líp c¸c CE cña c¸c thÆng d bËc 2 trong vµnh Z6 lµ mét nhãm ®Çy ®ñ ®èi víi
phÐp céng vµ nöa nhãm ®èi víi phÐp nh©n.
- Líp c¸c CE trong vµnh Z6 tho m·n c¸c tiªn ®Ò vÒ vµnh, chóng t¹o nªn mét
vµnh. §iÒu nµy còng ®óng cho c¸c phÇn tö liªn hîp cña mäi vµnh ®a thøc Z2n
víi c¸c n kh¸c nhau.
2. X©y dùng m· XCB theo c¸c ph©n tö liªn hîp cña luü ®¼ng nuèt
2.1 X©y dùng m· theo líp CEs cña luü ®¼ng nuèt trªn vµnh Z10 theo ph©n
ho¹ch chuÈn
Häc viÖn C«ng nghÖ BCVT
LÜnh vùc C«ng nghÖ th«ng tin
Theo kÕt qu
phÇn trªn ta thÊy
líp c¸c phÇn tö liªn hîp trªn Z2n lu«n cã cÊu tróc cña mét vµnh ®¹i sè, dùa vµo cÊu
tróc ®¹i sè nµy ta hoµn toµn cã thÓ x©y dùng ®îc m· XCB.
Trong vµnh
1x]x[Z n
2+
lu«n tån t¹i
∑
−
=
=1n
0i
i
0x)x(e
®îc gäi lµ luü ®¼ng
nuèt. T¬ng tù nh vËy, trong vµnh Z2n, ta còng x¸c ®Þnh ®îc mét lòy ®¼ng nuèt
lµ
)x(e 2
0
víi :
∑
−
=
=
1n
0i
i22
0
x)x(e
(2.1)
PhÐp nh©n mét ®a thøc bÊt kú víi luü ®¼ng nuèt gióp ta kiÓm tra ®îc
tÝnh ch½n lÎ. Luü ®¼ng nuèt cã nh÷ng tÝnh chÊt ®Æc biÖt ®Ó x©y dùng m·
XCB.
Trong vµnh
1x]x[Z 10
2+
, tøc vµnh Z2n víi n = 5 ta thÊy r»ng cã tÊt c¶ 32
(2n) thÆng d bËc 2 mçi thÆng d bËc 2 cã tÊt c¶ 32 (2n) phÇn tö liªn hîp. C¸c
thÆng d bËc 2 trong vµnh lµ c¸c ®a thøc bao gåm c¸c ®¬n thøc cã sè mò ch½n ®-
îc x¸c ®Þnh nhê bæ ®Ò 1.1.
Q10 = {0, 1, x2, x4, x6, x8, 1+x2, 1+x4, 1+x6, 1+x8, x2+x4, x2+x6, x2+x8, x4+x6, x4+x8, x6+x8,
1+x2+x4, 1+x2+x6, 1+x2+x8, 1+x4+x6, 1+x4+x8, 1+x6+x8, x2+x4+x6, x2+x4+x8, x2+x6+x8, x4+x6+x8,
1+x2+x4+x6, 1+x2+x4+x8, 1+x2+x6+x8, 1+x4+x6+x8, x2+x4+x6+x8, 1+x2+x4+x6+x8}
C¸c phÇn tö liªn hîp cña luü ®¼ng nuèt e0(x 2
)=1+x 2
+x 4
+x 6
+x 8
Ta x¸c ®Þnh CEs cña luü ®¼ng nuèt e0(x2)=1+x2+x4+x6+x8 trong tËp Q10 trªn
theo biÓu thøc:
Sqr(e0(x2)) = (1+xn)
∑
∈Ut
t
x
+
2
0
( )e x
(2.2)
Toµn bé c¸c phÇn tö liªn hîp cña luü ®¼ng nuèt ®îc thÓ hiÖn ë b¶ng bªn
tr¸i, bng bªn phi thÓ hiÖn ph©n ho¹ch cña c¸c luü ®¼ng nuèt trong vµnh Z10
theo ph©n ho¹ch chuÈn (ph©n ho¹ch trong ®ã c¸c phÇn tö trong mét líp dÞch
vßng theo c¸c tr ëng líp kÒ) .
Häc viÖn C«ng nghÖ BCVT