Khảo sát mã Xiclic vành đa thức X9+1: Tổng hợp [Năm hiện tại]

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 x9 + 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

[ ]

Z x x 1

), 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· 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]/ xn + 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]/ xn +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]/xn +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 = {

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 xn + 1

Gi¸ trÞ cña m ®îc x¸c ®Þnh bëi cÊp cña nhãm nh©n xyclic.

2. CÊu tróc c¸c nhãm nh©n xyclic trong vµnh ®a thøc Z2[x] /x9 + 1

2.1. CÊu tróc c¸c nhãm nh©n

Víi vµnh Z2[x]/ x9 + 1, ta cã n = 9 (lµ sè lÎ).

+ Khai triÓn nhÞ thøc: x9 + 1 = (1 + x)(1 + x + x2)(1 + x3 + x6).

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 ms = 6, hay cÊp lín nhÊt cña ®a thøc bÊt kh¶

quy trong khai triÓn nhÞ thøc x9 +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:

{ }

, .2, .2 ,..., .2

C s s s s

−

trong ®ã

−

≡ s mod n

C0 = {0} →|C 0| = m0 = 1

C1 = {1, 2, 4, 8, 7, 5} →|C 1| = m1 = 6

C3 = {3, 6} →|C 3| = m3 = 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 Z2[x]/ x9 + 1

C¸c lòy ®¼ng D¹ng sè mò

cña ®a thøc

C¸c chu tr×nh

t¬ng øng

e1(x) = 1 + x + x2 + x4 + x5 + x7 + x8(0124578) C0 ∪ C1

e2(x) = 1 + x3 + x6(036) C0 ∪ C3

e3(x) = e0(x) = 1 + x + x2 + x3 + x4 + x5 + x6 + x7 + x8(012345678) C0 ∪ C1 ∪ C3

e4(x) = 1 (0) C0

e5(x) = x3 + x6(36) C3

e6(x) = x + x2 + x4 + x5 + x7 + x8(124578) C1

e7(x) = x + x2 + x3 + x4 + x5 + x6 + x7 + x8(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:

oX¸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.

oChä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

3. Kh ¶o s¸t mét sè m· xyclic vµ xyclic côc bé trªn vµnh ®a thøc X9 + 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

( )

0,1, 2,..., 1

x i k= −

vµ lµ nhãm

[ ]

( )

/ 1

Z x x +

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

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é

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.

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.

+ 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

( )

1; 1

n n

x g x x+ +

−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:

0 1 2 1

... 0

x x x x

−

= = = = =

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.

{ }

, 1, 1

I x i m= = −

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 ®Ó

Häc viÖn C«ng nghÖ BCVT

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

Chủ đề:

Tài liệu liên quan

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi