Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng

in rằng văn bản xuất phát từ người sở hữu khóa bí mật. Cả hai bên 
tham gia vào quá trình thông tin đều có thể tin tường là văn bản không bị sửa đổi 
trong khi truyền vì nếu văn bản bị thay đổi thì mã băm sẽ thay đổi và lập tức bị 
phát hiện. 
 47 
Các bước tạo chữ ký và kiểm tra chữ ký được mô tả trên hình sau: 
 Hình 1.17. Quá trình tạo chữ ký số và kiểm tra chữ ký số 
 Ví dụ 1.6: Sơ đồ chữ ký số sử dụng RSA như hình 1.18. 
 Hình 1.18. Sơ đồ chữ ký số dùng RSA 
 48 
 Quá trình ký: 
 Băm thông báo M để có mã băm: HHMMDC () 
 Mã hóa mã băm HMDC bằng hệ mật RSA với khóa bí mật của A (dA): 
 dA
 DSAA H( M ) mod n được chữ ký số của DSA. 
 Ghép chữ ký số DSA với thông báo: M|| DSA và truyền đi. 
Quá trình kiểm tra: 
 Tách thông báo M và chữ ký số DSA. 
 Giải mã RSA chữ ký số bằng khóa công khai của A (eA) để thu được mã 
 băm của bên phát. 
 Tiến hành băm M để tạo mã băm độc lập: HMDC và so sánh với mã băm 
 bên phát. 
Nhận xét: Sơ đồ này không bảo mật thông báo M. 
 Để bảo mật thông báo người ta sử dụng sơ đồ chữ ký số dạng như hình 1.19. 
 Hình 1.19. Sơ đồ chữ ký số dùng RSA và có bảo mật thông báo 
 49 
1.6. KẾT LUẬN CHƯƠNG 1 
 Trong chương 1, luận văn tập trung tìm hiểu các vấn đề chung nhất về mật 
mã khóa bí mật (hay còn gọi là mật mã cổ điển); mật mã khóa công khai (hay mật 
mã hiện đại) và hàm băm, từ đó phân tích các ưu và nhược điểm của từng hệ mật. 
 Các nghiên cứu về cấu trúc nhóm nhân và cấp số nhân cyclic trên vành đa 
thức cho các kết quả khá lý thú trong việc xây dựng các mã sửa sai và mật mã. Để 
tăng chiều dài cho mật mã khối có thể sử dụng cấu trúc các cấp số nhân cyclic 
trong các hàm mật mã, nội dung này sẽ được trình bày trong chương 2. 
 50 
 CHƯƠNG 2. HỆ MẬT XÂY DỰNG TRÊN 
 CÁC CẤP SỐ NHÂN CYCLIC 
2.1. NHÓM NHÂN CYCLIC TRÊN VÀNH ĐA THỨC 
2.1.1. Định nghĩa nhóm nhân cyclic trên vành đa thức 
Định nghĩa 2.1 [6], [10]: 
 Nhóm nhân cyclic (CMG-Cyclic Multiplicate Group) 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 cyclic, số nhóm nhân bằng số các lũy đẳng có 
thể có trong vành. 
 A { , 23 , ..., m } (2.1) 
 Trong đó: 
 A là nhóm nhân cyclic 
 là phần tử sinh (đa thức sinh), . 
 m là cấp của nhóm nhân, cũng chính là cấp của phần tử sinh . 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 ex() có cấp bằng 1. 
 Định nghĩa 2.2 [6], [10]: 
 n
 Trong vành đa thức Z2[xx ]/ 1, nếu tồn tại một đa thức mà bình phương 
của nó lại bằng chính nó thì được gọi là đa thức lũy đẳng và ký hiệu là ex(). 
 22
 e()()() x e x e x (2.2) 
 Các lũy đẳng ex() được xác định trên cơ sở phân tích chu trình Cs . 
 n 1
 n i
 Trong mỗi vành đa thức Z2[xx ]/ 1 đều tồn tại một lũy đẳng e0 () x  x , 
 i 0
lũy đẳng này được gọi là lũy đẳng “nuốt” (Swallowing Idempotent). 
 51 
 Trong một vành bất kỳ, với n lẻ luôn tồn tại một lớp kề chỉ chứa một lũy 
đẳng “nuốt” ex0 (). 
 * Tính chất của lũy đẳng “nuốt” 
 n
 - Nếu đa thức a( x ) Z2 [ x ]/ x 1 và trọng số của ax() (ký hiệu là W( a ( x )) ) 
 là số lẻ thì a( x ). e00 ( x ) e ( x ). 
 n
 - Nếu đa thức b( x ) Z2 [ x ]/ x 1 và W( b ( x ))là số chẵn thì b( x ). e0 ( x ) 0. 
 * Các chu trình Cs 
 Các chu trình Cs theo modulo n trên trường GF(2) được xác định như sau: 
 2 ms 1 ms 1
 Cs s, s .2, s .2 ,..., s .2  trong đó s.2 s mod n 
 Khi đó tập các số nguyên theo modulo n được phân hoạch thành các chu 
trình. Ta có: {0,1,2,3,...,nC } s 
 s
 * Ý nghĩa của các chu trình: 
 n
 Số các chu trình cho ta biết số các đa thức bất khả quy trong vành Z2[xx ]/ 1 
 Lực lượng của các chu trình cho ta biết bậc của đa thức bất khả quy tương 
 ứng trong phân tích của nhị thức xn 1. 
 Các số trong một chu trình cho biết số mũ tương ứng của đa thức lũy đẳng ex() 
 Định lý 2.1: Cấp của một đa thức ax(), (ký hiệu ord( a ( x )) ), là số nguyên 
dương m nhỏ nhất thỏa mãn [6], [7], [10]: 
 amn( x ) e ( x )mod( x 1) (2.3) 
 Trong đó ex() là một lũy đẳng nào đó. 
 Như vậy ax() sẽ tạo nên một nhóm cyclic cấp m của vành. 
 Định lý 2.2: Nếu ax() là phần tử của nhóm nhân nào đó thì cấp cực đại của 
ax() được xác định như sau [6], [7], [8], [10]: 
 52 
 n 1
 - Nếu n lẻ và x 1 fi ( x ) ; trong đó fxi () là các đa thức bất khả quy. 
 m
 Khi đó max ord(ax ( )) 2 1, với m maxdeg fi ( x ) . 
 s 21k 
 - Nếu n chẵn nk 2 (2 1) và x 1 fi ( x ) . 
 sm
 Khi đó max ord(ax ( )) 2 (2 1) , với m maxdeg fi ( x ) . 
 n k
 Bổ đề 2.1: Trong vành Z2[xx ]/ 1với n 2 ( k nguyên dương), tập các đa 
thức có trọng số lẻ sẽ tạo nên một nhóm nhân G các đa thức theo modulo xn 1 
[7], [8], [9]. 
 Bổ đề 2.2: Mọi phần tử trong nhóm nhân G có cấp là 2k hoặc có cấp là ước 
của 2k [7], [8], [9] [11], [12]. 
 Bổ đề 2.3: Số các thặng dư bậc hai trong nhóm nhân G của vành được xác 
định như sau [7], [8], [9]: 
 k 1
 Q 221 (2.4) 
* Các phần tử cấp n và các nhóm nhân cyclic cấp n. 
 i
 Xét a() x G . a() x  ai x . Ta có bổ đề sau: 
 Bổ đề 2.4: Đa thức ax() là phần tử cấp n khi nó có chứa một số lẻ các đơn 
thức có mũ lẻ có cấp n và một số chẵn các đơn thức có mũ chẵn có cấp là ước của 
n. Số các đa thức cấp n bằng 2n 2 [1]. 
 Ví dụ 2.1: Với n = 8, có tất cả 26 64 các phần tử cấp n. Ta có thể sử dụng 
các phần tử này để xây dựng các nhóm nhân cyclic cấp n . 
 2 3nn 1 0
 Ai {(), axaxax i i (), i (), a i (), xaxax i () i ()1} 
 Có tất cả 2n 2 các nhóm nhân cyclic cấp n và nhóm nhân I cũng thuộc vào 
lớp các nhóm nhân này. Ta gọi I là nhóm nhân cyclic đơn vị. 
2.1.2. Các loại nhóm nhân cyclic trên vành đa thức 
2.1.2.1. Nhóm nhân cyclic đơn vị 
Định nghĩa 2.3: Nhóm nhân cyclic đơn vị là một nhóm nhân bao gồm mọi đơn 
thức có trong vành và nó có cấp là n. Ký hiệu là I { x , x21 ,..., xn ,1} [4], [6]. 
 53 
 Hay nói cách khác nhóm nhân cyclic đơn vị là nhóm nhân cyclic có phần tử sinh 
là x. 
 I { x ,( x )2 ,( x ) 3 ...,( x )n 1 ,1} 
2.1.2.2. Nhóm nhân cyclic với phần tử sinh ax() 
Định nghĩa 2.4: Nhóm nhân cyclic với phần tử sinh là đa thức ax() 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 sau [6], [10]: 
 A ( a ( x ), a23 ( x ), a ( x ),..., am ( x )} (2.5) 
 Trong đó: m là cấp của ax(). 
2.1.2.3. Đa thức đối xứng và các nhóm nhân cyclic đối xứng 
Định nghĩa 2.5: (Đa thức đối xứng) [6], [10] 
 Đa thức ax()được gọi là đa thức đối xứng với đa thức ax() nếu: 
 i j
 a() x  ai x thì a() x  aj x ax() 
 iI jJ 
 Với: I J= ; I J S 0,1,..., n 1 . 
Bổ đề 2.5: Nếu ax() là một phần tử cấp k thì cấp của ax() cũng bằng k . Tức là, 
nếu A là một nhóm nhân cyclic cấp có phần tử sinh là ax() thì A cũng là nhóm 
nhân cyclic cấp với phần tử sinh là ax() [6], [10]. Khi đó ta có: 
 A { a ( x ), a2 ( x ), a 3 ( x ),..., ak 1 ( x )} 
 A { a ( x ),( a ( x ))2 ,( a ( x )) 3 ,...,( a ( x ))k 1 } (2.7) 
 Như vậy, với mỗi phần tử ax() của nhóm nhân cyclic A ta có tương ứng một 
phần tử ax() của nhóm nhân cyclic A. Từ nhóm nhân cyclic A ta dễ dàng thiết lập 
được nhóm nhân cyclic A. Hai nhóm nhân A và A được gọi là hai nhóm nhân 
cyclic đối xứng trong vành đa thức. 
 Từ việc khảo sát các nhóm nhân đối xứng trong vành đa thức ta thấy chỉ cần 
khảo sát các nhóm nhân trong một nửa vành là ta có thể suy ra kết quả khảo sát 
 54 
cho toàn bộ vành. Khi coi mỗi nhóm nhân là một mã tương ứng mà ta có thể xây 
dựng được trên nó, ta sẽ khảo sát được các mã trên vành. 
2.2. CẤP SỐ NHÂN CYCLIC TRÊN VÀNH ĐA THỨC 
2.2.1. Khái niệm về cấp số nhân cyclic trên vành đa thức 
 n
 Xét vành đa thức Z2[xx ]/ 1 với n lẻ. 
Định nghĩa 2.6: 
 Cấp số nhân cyclic (CGP - Cyclic Geometic Progressions) trên vành đa thức 
là một tập hợp con có dạng sau [6], [10]: 
 21m 
 A(,)aq {(), axaxqxaxqx ()(), () (),..., axq () ()} x (2.8) 
 Trong đó: m là số các số hạng của cấp số nhân. 
 ax()là số hạng đầu của cấp số nhân. 
 qx() là công bội. 
 a( x ) qmn ( x ) a ( x )mod x 1 
 Giá trị của m chính là cấp của nhóm nhân sinh với phần tử sinh qx() và lũy 
đẳng qxm (). Cấp lớn nhất của phần tử qx()được xác định bởi định lý 2.2. 
 Trong trường hợp ta chọn số hạng đầu ax( ) 1, công bội là qx() thì 
 21m 
 A(1,q ) {1, q ( x ), q ( x ),..., q ( x )} 
 q( x ) q0 ( x ) 1 
 Là một cấp số nhân cyclic cấp m. 
 n
 Như vậy, trong vành đa thức Z2[ x ] / x 1, nếu ta chọn số hạng đầu ax()và hạt 
nhân phân hoạch qx() khác nhau thì ta sẽ tạo ra nhiều kiểu phân hoạch khác nhau 
của vành, do đó ta có các cấp số nhân cyclic để xây dựng được các mã cyclic có 
cấu trúc khác nhau. 
 * Các cấp số nhân cyclic cấp n 
 55 
 Nếu ta nhân các phần tử của một nhóm nhân cyclic cấp n với một phần tử bất 
kỳ trong nhóm nhóm nhân G của vành đa thức ta sẽ thu được một cấp số nhân có 
công bội là phần tử sinh của nhóm nhân và có số hạng ban đầu là đa thức đem 
nhân. 
 Bổ đề 2.6: Số các cấp số nhân cyclic cấp n xây dựng được trong G trên vành 
 k
x2 1 ( nguyên dương) được xác định như sau [7], [8], [9]: 
 k
 kk
 N 22 2 .2 2 2 (2.9) 
Ví dụ 2.2: 
 n Số cấp số nhân N n Số cấp số nhân N 
 n 8 N 28 1 .2 8 2 2 13 8.192 n 64 N 264 1 .2 64 2 2 125 
 n 16 N 216 1 .2 16 2 2 29 65.011.712 n 32 N 232 1 .2 32 2 2 61 
2.2.2. Phân hoạch vành đa thức 
 Quá trình phân hoạch vành đa thức thực chất là quá trình phân chia các phần 
tử trong vành đa thức thành các tập (hay các lớp kề) không trùng nhau. Các phần 
tử sinh của nhóm nhân sinh được gọi là các hạt nhân của phân hoạch. Trong mỗi 
phân hoạch vành đa thức, các lớp kề của nó là các cấp số nhân cyclic với cùng một 
công bội. 
2.2.2.1. Các bước phân hoạch vành đa thức 
 Để phân hoạch một vành đa thức ta thực hiện theo các bước sau đây [6], [7]: 
 n
 Bước 1: + Chọn một phần tử sinh a( x ) z Z2 [ x ] / x 1. 
 + Xây dựng nhóm nhân cyclic: A { ai ( x ), i 1,2,..., m }, 
 trong đó: m ord a ( x ) . 
 + SA ; 
 n
 Bước 2: + Chọn b( x ) {¢ 2 [ x ]/ x 1\ S }. 
 + Xây dựng cấp số nhân cyclic: 
 B b( x ). A { b ( x ). ai ( x ), i 1,2,..., m } 
 + SSB 
 56 
 n
 Bước 3: Lặp lại bước 2 cho đến khi S Z2[ x ]/ x 1 
 Thông số m là cấp của ax() được xác định theo định lý 2.1. Giá trị m chỉ có 
thể bằng max ord ax ( ) hoặc ước số của . 
 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. Vì vậy khi phân 
hoạch ta chỉ cần tìm các phần tử có trọng số lẻ của vành rồi có thể dễ dàng suy ra 
các phần tử chẵn. 
 Để xây dựng được tất cả các nhóm nhân của vành ta thực hiện các bước sau: 
 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. 
 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 cyclic 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. 
2.2.2.2. Phân hoạch vành đa thức suy biến và không suy biến 
 Có nhiều dạng phân hoạch vành đa thức khác nhau, song dạng phân hoạch 
chung nhất là phân hoạch suy biến và phân hoạch không suy biến. 
Định nghĩa 2.7: 
 Phân hoạch vành đa thức được gọi là không suy biến nếu phân hoạch bao 
gồm tất cả các phần tử khác 0 trong vành đa thức. Ngược lại, phân hoạch là phân 
hoạch suy biến [6]. 
 Bổ đề 2.7: Trong một phân hoạch không suy biến tùy ý, số lớp kề trong phân 
hoạch xác định theo biểu thức sau [6]: 
 22n 
 N(a ( x ), n ) 1 (2.10) 
 ord( a ( x ))
 * Điều kiện để phân hoạch không suy biến 
 57 
 Định lý 2.3: Điều kiện cần và đủ để phân hoạch vành không suy biến là nhóm 
nhân sinh của phân hoạch có lũy đẳng bằng 1 [6]. 
 Bổ đề 2.8: Số kiểu phân hoạch không suy biến khác nhau bằng số các bậc 
khác nhau của các phần tử trong vành (trừ các phần tử lũy đẳng có bậc là 1), ký 
hiệu là M [6]. 
 Số kiểu phân hoạch không suy biến khác nhau chính là số ước khác nhau của 
giá trị cấp lớn nhất của phần tử a(x) (max ord a(x)). Giá trị max ord a(x) . 
 Kết quả tính số kiểu phân hoạch không suy biến M của một số vành được 
thống kê trong bảng 2.1. 
 Bảng 2.1. Số kiểu phân hoạch không suy biến M của một số vành 
 n max ord ax() Phân tích của max ord ax() M 
 5 15 3.5 3 
 7 7 7 1 
 9 63 3.3.7 5 
 11 1023 3.11.31 7 
 13 4095 3.3.5.7.13 16 
 15 15 3.5 3 
 Bổ đề 2.9: Số kiểu phân hoạch suy biến (ký hiệu là I) bằng số Ideal trong 
vành đa thức [6]. 
 n
 Trong vành đa thức Z2[xx ]/ 1, số Ideal của vành được xây dựng tương 
ứng với các đa thức sinh gx(), mỗi Ideal tương ứng với bộ mã cyclic (theo quan 
điểm xây dựng mã cyclic cổ điển). 
 Các đa thức sinh gx()tương ứng với mỗi Ideal được lập từ tổ hợp các đa 
thức bất khả quy trong phân tích của nhị thức xn + 1. 
 t
 n
 x 1  fit ( x ) f12 ( x ). f ( x )... f ( x ) , với degfi ( x ) n 
 i i 1
 58 
 s
 n 
 g() x  fjs () x f12 ().()...() x f x f x , với gx() | x + 1, degfj ( x ) n 
 j j 1
 Như vậy, số đa thức sinhI g({x x) ,( (tương x )2 ,( x )ứ 3ng ...,( là x )Ideal)n 1 ,1} có thể thiết lập được từ t đa 
 t 1
 n i
thức bất khả quy trong phân tích nhị thức x + 1 được xác định: I Cm . 
 i 1
 Bổ đề 2.10: Tổng số các kiểu phân hoạch có trong một vành đa thức (ký hiệu 
là C) được xác định bởi biểu thức: C=M.I [6]. 
 n n
 Tổng số các kiểu phân hoạch C của một số vànhZ2[xx ]/Z2[xx ]/ 1 1 khác nhau như 
trong trong bảng 2.2. 
 Bảng 2.2. Tổng số các kiểu phân hoạch của vành 
 Số đa thức bất khả quy 
 n M I C = M.I 
 trong phân tích xn + 1 
 5 2 3 2 6 
 7 3 1 6 6 
 9 3 5 6 30 
 11 2 7 2 14 
 13 2 16 2 32 
 15 5 3 30 90 
 n
 Như vậy, trong một vành đa thức Z2[xx ]/ 1, với mỗi giá trị n thì số kiểu 
phân hoạch cũng khá nhiều, tạo ra khả năng lớn để chọn dạng mã cyclic có đặc 
tính sửa sai tốt. Trong mỗi dạng mã đã xác định, ta tiến hành lựa chọn các mã sửa 
sai tối ưu để sử dụng. 
2.2.2.3. Các loại phân hoạch 
a) Phân hoạch chuẩn 
 Phân hoạch chuẩn hay phân hoạch theo I – nhóm nhân cyclic đơn vị [6]. 
 (2.11) 
 Hạt nhân của phân hoạch là x, có cấp ord(xn ) . 
 59 
 + Các lớp kề có độ lớn bằng n hoặc ước của n. 
 Bổ đề 2.11: Trong phân hoạch chuẩn thì số lớp kề trong phân hoạch được xác 
định theo biểu thức [6]: 
 22n 
 N(,)xn 1 (2.12) 
 n
 + Khi n là số nguyên tố thì có thể tính chính xác được số lớp kề. 
 n 1
 i
 Có một lớp kề chỉ chứa e0 x  x , số phần tử còn lại trong các lớp kề là 
 i 1
 22n 
22n . Do đó số các lớp kề là: N 1. 
 n
b) Phân hoạch cực đại 
Định nghĩa 2.8: 
 Phân hoạch được gọi là cực đại nếu nhóm nhân cyclic sinh có phần tử sinh 
 n
với cấp lớn nhất, ord a ( x ) maxord b ( x ); b ( x ) Z2 [ x ]/ x 1 [6]. 
 Bổ đề 2.12: Trong phân hoạch cực đại thì số lớp kề của phân hoạch được xác 
định theo công thức sau [6]: 
 22n 
 N(a ( x ), n ) 1 (2.13) 
 maxord ( b ( x ))
c) Phân hoạch cực tiểu 
 Định nghĩa 2.9: Phân hoạch là cực tiểu (hay phân hoạch tầm thường) là phân 
hoạch có phần tử sinh của nhóm nhân cyclic là ax( ) 1 [6]. 
 Bổ đề 2.13: Trong phân hoạch cực tiểu với phần tử của nhóm nhân ax( ) 1, 
số lớp kề trong phân hoạch được xác định [6]: 
 n
 N(1,n ) 21 (2.14) 
 Trong phân hoạch cực tiểu, mỗi lớp kề chỉ gồm 1 phần tử, do vậy số lớp kề 
trong phân hoạch này đúng bằng số phần tử khác 0 có trong vành: 2n – 1 . 
 60 
d) Phân hoạch vành thành các cấp số nhân có cùng trọng số 
 i i
 Trong trường hợp q() x x và ord(xn ) thì cấp số nhân A(,)aq bao gồm 
các đa thức có cùng trọng số. Vành đa thức được phân hoạch thành các cấp số 
nhân với các phần tử trong mỗi cấp số nhân sẽ có cùng trọng số. 
 Dạng phân hoạch này chính là phân hoạch không suy biến và phân hoạch 
theo nhóm nhân đơn vị. 
e) Phân hoạch vành thành các phần tử có trọng số cùng tính chẵn lẻ. 
 Xét cấp số nhân cyclic có dạng sau [6]: 
 21m 
 A(,)aq {(), axaxqxaxqx ()(), () (),..., axq () ()} x (2.15) 
 - Nếu W( q ( x )) lẻ. 
 + Phần tử đầu tiên ax() là đa thức có trọng số lẻ thì tất cả các phần tử của 
 cấp số nhân đều là đa thức có trọng số lẻ. Vì tích của các đa thức có 
 trọng số lẻ là một đa thức có trọng số lẻ. 
 + Phần tử đầu tiên ax() là đa thức có trọng số chẵn thì tất cả các phần tử 
 của cấp số nhân đều là đa thức có trọng số chẵn. 
 Vậy khi lẻ các lớp kề có các đa thức có trọng số chẵn hoặc lẻ. 
 - Nếu chẵn, với phần tử đầu tiên ax() là đa thức bất kỳ thì tất cả các 
phần tử của cấp số nhân đều là đa thức có trọng số chẵn phân hoạch suy biến. 
 Tóm lại, nếu công bội qx() (hạt nhân phân hoạch) là một đa thức có trọng số 
lẻ thì các phần tử của mỗi cấp số nhân trong phân hoạch sẽ cùng tính chẵn lẻ về 
trọng số. 
f) Phân hoạch vành đa thức thành các cấp số nhân theo modulo h(x). 
 n
 Vành đa thức Z2[xx ]/ 1 có thể được phân hoạch thành các cấp số nhân 
theo modulo hx() với h( x ) | xn 1 [6], [7], [8]. 
 n
 Từ phân tích nhị thức x 1 f12 ( x ). f ( x )... ft ( x ) 
 61 
 Trong đó, fi(x) là các đa thức bất khả quy. 
 Như vậy, hx() là tổ hợp của các fi(x) sao cho deg degh ( x ) k n. Tuỳ theo 
giá trị n mà có số đa thức bất khả quy khác nhau, nên sẽ có số hx()khác nhau. Khi 
đó, trên vành sẽ có nhiều phân hoạch ứng với các hx()khác nhau. 
 Trong trường hợp này phân hoạch vành chỉ gồm 2k – 1 phần tử cho nên phân 
hoạch sẽ suy biến và vành đa thức bị suy biến thành các vành nhỏ hơn. 
2.3. XÂY DỰNG M-DÃY LỒNG GHÉP TRÊN VÀNH ĐA THỨC CÓ HAI LỚP 
 KỀ CYCLIC 
2.3.1. Vành đa thức có hai lớp kề 
Định nghĩa 2.10 
 Vành đa thức theo modulo xn 1 được gọi là vành đa thức có hai lớp kề 
cyclic nếu phân tích của thành tích của các đa thức bất khả quy trên trường 
GF(2) có dạng sau [2]: 
 n 1
 xni 1 (1 x ) x (2.16) 
 i 0
 n 1
 i
 Trong đó và e0 () x  x là các đa thức bất khả quy. 
 i 0
Bổ đề 2.14 
 Vành đa thức theo modulo là một vành đa thức có hai lớp kề cyclic nếu 
n thoả mãn [2], [7], [8]: 
 n phải là một số nguyên tố; 
 phần tử thứ hai phải thoả điều kiện 2 (np )/ 1modn với mỗi ước nguyên 
 tố p của (n). (Trong đó (n) là hàm phi Euler) 
Thuật toán xác định giá trị n [8], [9], [10], [11] 
 Vào: số nguyên tố n 
 Bước 1: tìm phân tích của (n-1); 
 xác định các ước nguyên tố pi của phân tích này. 
 62 
 n 1/ pi
 Bước 2: với mỗi pi tính 2 
 np 1/ i
 - Nếu tồn tại pi sao cho 2 1(modn ) thì n không thoả mãn. 
 - n thoả mãn trong các trường hợp còn lại. 
 Ra: Giá trị n thoả mãn. 
 Theo thuật toán này ta xác định được một số giá trị n đảm bảo vành đa thức 
theo mod xn+1 là một vành đa thức có hai lớp kề cyclic. 
 Dưới đây là một số giá trị n thỏa mãn. 
 n = 3 5 11 13 19 29 37 53 59 61 67 83 101 107 131 139 149 163 173 179 181 197 211 227 
269 293 317 347 349 373 379 389 419 421 443 461 467 491 509 523 541 547 557 563 587 613 
619 653 659 661 677 701 709 757 773 787 797 821 827 829 853 859 877 883 907 941 947 1019 
1061 1091 1109 1117 1123 1171 1187 1213 1229 1237 1259 1277 1283 1291 1301 1307 1373 
1381 1427 1451 1453 1483 1493 1499 1523 1531 1549 1571 1619 1621 1637 1667 1669 1693 
1733 1741 1747 1787 1861 1867 1877 1901 1907 1931 1949 1973 1979 1987 1997 2027 2029 
2053 2069 2083 2099 2131 2141 2213 2221 2237 2243 2267 2269 2293 2309 2333 2339 2357 
2371 2389 2437 2459 2467 2477 2531 2539 2549 2557 2579 2621 2659 2677 2683 2693 2699 
2707 2741 2789 2797 2803 2819 2837 2843 2851 2861 2909 2939 2957 2963 3011 3019 3037 
3067 3083 3187 3203 3253 3299 3307 3323 3347 3371 3413 3461 3467 3469 3491 3499 3517 
3533 3539 3547 3557 3571 3581 3613 3637 3643 3659 3677 3691 3701 3709 3733 3779 3797 
3803 3851 3853 3877 3907 3917 3923 3931 3947 3989 4003 4013 4019 4021 4091 4093 4099 
4133 4139 4157 4219 4229 4243 4253 4259 4261 4283 4349 4357 4363 4373 4397 4451 4483 
4493 4507 4517 4547 4603 4621 4637 4691 4723 4787 4789 4813 4877 4933 4957 4973 4987 
5003 5011 5051 5059 5077 5099 5107 5147 5171 5179 5189 5227 5261 5309 5333 5387 5443 
5477 5483 5501 5507 5557 5563 5573 5651 5659 5683 5693 5701 5717 5741 5749 5779 5813 
5827 5843 5851 5869 5923 5939 5987 6011 6029 6053 6067 6101 6131 6173 6197 6203