Tóm tắt Luận án Nhóm nhân cyclic và mã cyclic trên vành đa thức

ên chỉ tới khi được xây dựng trên các vành đa thức vào năm 1996 các nghiên cứu về mã LCC mới được thúc đẩy mạnh mẽ và thu được nhiều kết quả khích lệ về: phân hoạch vành đa thức, mã LCC tự trực giao, mã LCC có khả năng trực giao, mã LCC đối xứng và tự đối xứng, các mã cyclic trên vành đa thức có 2 lớp kề cyclic,... Các công trình này đều có ý nghĩa về mặt lý thuyết, đạt được những thành tựu và kết quả nhất định. Tuy nhiên, lý thuyết và thực nghiệm về mã cyclic cục bộ và mã cyclic trên vành đa thức vẫn chưa hoàn thiện và có một số hướng nghiên cứu mở. Nghiên cứu sinh xác định luận án nghiên cứu việc kiến thiết nhóm nhân cyclic có cấp cực đại, mối quan hệ của mã cyclic cục bộ (mã cyclic xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic trên vành đa thức) với mã cyclic truyền thông, phương pháp lựa chọn mã cyclic tốt, ứng dụng của nhóm nhân cyclic, cấp số nhân cyclic trong mã sửa lỗi, mật mã, và khả năng thực hiện các bộ mã cyclic trên cấu kiện phần cứng. 1.6. KẾT LUẬN CHƯƠNG Trong chương này, Luận án đã trình bày cơ sở lý thuyết cho các nội dung nghiên cứu của luận án bao gồm các nội dung về vành đa thức, vành đa thức có hai lớp kề cyclic, tính chất đa thức, chu trình, luỹ đẳng, mã tuyến tính, mã cyclic truyền thống, một số tiêu chuẩn đánh giá mã tuyến tính, nhóm nhân cyclic, cấp số nhân cyclic, phân hoạch vành đa thức và mã cyclic cục bộ. Ở cuối chương trình bày hướng nghiên của của luận án và thảo luận một số kết quả nghiên cứu liên quan từ đó làm rõ hơn nội dung nghiên cứu của luận án. 5 CHƯƠNG 2 CẤP CỦA ĐA THỨC VÀ QUAN HỆ GIỮA NHÓM NHÂN CYCLIC, CẤP SỐ NHÂN CYCLIC VỚI MÃ CYCLIC TRUYỀN THỐNG Tóm tắt: Trong chương này, Luận án trình bày các kết quả nghiên cứu về phương pháp kiến thiết nhóm nhân cyclic có cấp cực đại, mối quan hệ giữa nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống góp phần bổ sung và hoàn thiện lý thuyết về mã cyclic. Nội dung chương 2 được bố cục gồm ba phần và kết luận chương. Phần đầu tiên giới thiệu chung về nội dung của chương và các vấn đề liên quan. Nội dung tiếp theo trình bày một số kết quả nghiên cứu mới của tác giả về cấp của đa thức. Phần cuối cùng trình bày kết quả nghiên cứu mới về mối quan hệ giữa nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống qua đó chứng minh được sự tương đương giữa nhóm nhân và cấp số nhân cyclic với mã cyclic truyền thống. 2.1. GIỚI THIỆU Đến thời điểm hiện tại, chưa có công trình nào tập trung nghiên cứu và có kết quả đầy đủ về cấp của đa thức, về kiến thiết nhóm nhân cyclic có cấp cực đại trên vành đa thức. Đặc biệt cũng chưa có tiêu chuẩn toán học nào cho việc tìm kiếm đa thức có cấp cực đại trên vành. Chính điều này gợi mở cho nghiên cứu sinh hướng nghiên cứu về xác định cấp của đa thức, từ đó kiến thiết nhóm nhân cyclic có cấp cực đại trên vành đa thức. Các kết quả nghiên cứu sẽ được trình bày chi tiết trong mục 2.2. Cũng trên cơ sở nghiên cứu về mã cyclic cục bộ (xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic trên vành đa thức), nghiên cứu sinh thấy rằng có thể tồn tại mối quan hệ giữa mã cyclic cục bộ (hay nhóm nhân cyclic, cấp số nhân cyclic) với mã cyclic truyền thống và việc chứng minh bằng toán học, khảo sát đánh giá mối quan hệ này hiện nay vẫn là một vấn đề mở cần được nghiên cứu. Việc chứng minh được mối quan hệ này sẽ góp phần làm sáng tỏ mối liên hệ và tạo ra cầu nối giữa các cách xây dựng mã cyclic khác nhau. Một kết quả nghiên cứu về vấn đề này được trình bày trong mục 2.3. Khi giải quyết được hai nội dung lý thuyết quan trọng như đề cập sẽ góp thêm sở cứ cho việc đề xuất một sơ đồ phân loại mã tuyến tính dựa trên cấu trúc đại số và mã cyclic cục bộ. 6 2.2. XÁC ĐỊNH CẤP CỦA ĐA THỨC Việc xác định được cấp của đa thức, đặc biệt cấp cực đại của đa thức có ý nghĩa quan trọng trong lý thuyết mã hóa. Nếu đa thức là phần tử sinh của nhóm nhân cyclic thì cấp đa thức chính là cấp của nhóm nhân, khi đa thức được sử dụng làm khóa trong các hệ mật thì ở góc độ nào đó cấp đa thức giúp xác định một phần độ phức tạp của hệ mật. Ngoài ra, xác định được cấp đa thức giúp chỉ ra bộ mã cyclic tối ưu, hoặc hạ bậc của đa thức để tạo ra bộ mã cyclic tối ưu xây dựng trên vành nhỏ hơn (chi tiết tại chương 3). Như vậy, trong nội dung nghiên cứu này luận án sẽ đề xuất một số phương pháp và thuật toán xác định cấp của đa thức trên vành, đồng thời cũng đề xuất đánh giá về xác suất chọn đa thức có cấp cực đại trên vành đa thức có hai lớp kề cyclic. 2.2.1. Đề xuất phương pháp xác định cấp của tích các đa thức Hiện tại vẫn chưa có phương pháp chung để xác định cấp của đa thức trên vành, do đó trong nội dung này luận án tập trung trình bày một hướng nghiên cứu xác định cấp của đa thức thông qua việc tìm cấp của đa thức là tích của các đa thức thông qua việc đề xuất và chứng minh đầy đủ hai bổ đề liên quan. Bổ đề 2.1: Xét đa thức 1 ( ) ( ) k i i g x f x   ; trong đó ( )if x là các đa thức có cấp tương ứng là 𝑚𝑖. Khi đó, cấp của ( )g x thỏa mãn [J5]:    1 2( ) , ,..., kord g x lcm m m m (2.1) Bổ đề 2.2: Xét 1 2 2( ), ( ) [ ] / ( 1) nxx f x xf   . Cấp của đa thức 1 2( ) ( ). ( )g x f x f x xác định như sau [J5]: 1) Trường hợp 1: Xét hai đa thức 1( ) ( ) if x a x và 2 ( ) ( ) jf x a x (hoặc 2 ( ) ( ) jf x a x ), ( ) CMG Aa x  cấp 𝑚 thì    1 2 ( ). ( ) gcd ,( ) m ord f x f x m i j   (2.2) 2) Trường hợp 2: Nếu 1 1( ) CMG Af x  và 2 2( ) CMG Af x  , với 1 2A A và không đối xứng nhau, cấp tương ứng của 1A , 2A là 1m , 2m    1 2 1 2( ). ( ) ,ord f x f x lcm m m (2.3) 7 Đặc biệt nếu  1 2gcd , 1m m  , thì  1 2 1 2( ). ( ) .ord f x f x m m Hệ quả: - Cấp của đa thức là tích hai đa thức bất kỳ thuộc cùng CMG hoặc hai CMG đối xứng không lớn hơn cấp cực đại của CMG đó. - Có thể tìm đa thức cấp cực đại bằng việc lấy tích của các đa thức có cấp là nguyên tố cùng nhau. 2.2.2. Đề xuất phương pháp xác định cấp của nhị thức Nhị thức là một đa thức có biểu diễn khá đơn giản và có khả năng đạt cực đại trên vành đa thức. Việc nghiên cứu cấp của nhị thức có thể tìm ra nhị thức đạt cấp cực đại hoặc làm cơ sở tìm đa thức có cấp phù hợp để nhân với nhị thức tạo thành đa thức có cấp cực đại. Trong phần này, luận án trình bày kết quả nghiên cứu về cấp của nhị thức thông qua đề xuất và chứng minh hoàn chỉnh một định lý, một bổ đề, đồng thời đề xuất một thuật toán xác định cấp nhị thức. Định lý 2.1: Cấp của nhị thức 1 jx trên 2[ ] / ( 1) nx x  được xác định [J3]: (1 | (2 1) ) v i imj iord x j C  í (2.5) Bổ đề 2.3: Trên vành đa thức 2[ ] / ( 1) nx x  [J5]. + Các nhị thức (1 ) jx với 1j C là các nhị thức có cấp lớn nhất. + Nhị thức (1 + 𝑥) có cấp cực đại trong số tất cả các nhị thức. Thuật toán xác định cấp của nhị thức (𝟏 + 𝒙) [J3] VÀO: Giá trị n RA: Cấp của nhị thức (1 + 𝑥) trên vành đa thức ( order ) 1. Chuyển nhị thức về mảng  a x có kích thước bằng giá trị 𝑛 của vành. 2. Đặt    g x a x và 1order  3. Lấy        , ,1g x XOR g x shift g x 4. So sánh  g x với  a x : 4.1. Nếu    g x a x thì 1order order  và lặp lại bước 2 4.2. Nếu    g x a x , dừng chương trình và in kết quả order 8 Thực hiện thuật toán xác định cấp của nhị thức (1 + 𝑥), thu được kết quả khảo sát trên một số vành đa thức [J3]. Từ kết quả chạy thuật toán, ta có thể nhận thấy rằng nhị thức (1 + 𝑥) có khả năng đạt cấp cực đại trên khá nhiều vành, do đó có thể lựa chọn làm phần tử sinh để tạo ra nhóm nhân đạt cấp cực đại trên những vành mà nhị thức này đạt cấp cực đại. Ngoài ra, ta có một phương pháp để tìm đa thức 𝑎(𝑥) có cấp cực đại từ nhị thức (1 + 𝑥), bằng cách chọn  ( ) 1 . ( ),a x x f x  (với điều kiện     gcd ( ) , 1 1ord f x ord x  ). Kết quả nghiên cứu này góp phần khẳng định rằng việc xác định đa thức đạt cấp cực đại trở nên khá dễ dàng, do đó bài toán quan trọng trong việc xây dựng các CMG có cấp cực đại đã có một hướng giải quyết mới và hiệu quả. Kết quả này được công bố trong [J3], [J5]. 2.2.3. Đề xuất thuật toán cải tiến để tìm và liệt kê cấp của đa thức trên vành Hai phương pháp được trình bày ở trên đã góp phần hoàn thiện lý thuyết và mở ra hướng tiếp cận mới. Trong phần này nghiên cứu sinh tiếp tục trình bày một phương pháp thực nghiệm đó là đề xuất thuật toán tìm và liệt kê cấp của đa thức trên vành. Thuật toán sử dụng phương pháp vét cạn để xác định cấp của tất cả các phần tử trên mỗi vành đa thức nên độ phức tạp thuật toán là khá cao, đặc biệt là đòi hỏi thời gian tính toán lớn và kém hiệu quả đối với các vành lớn. Trên cơ sở các tính chất của nhóm nhân cyclic, đa thức và cấp của đa thức đã trình bày trong chương 1, kết hợp một số bổ đề liên quan để xây dựng một thuật toán cải tiến giúp giảm độ phức tạp thuật toán, giảm thời gian tính toán trong việc tìm cấp của các đa thức. a) Ý tưởng chủ đạo của thuật toán là sử dụng các kết quả nghiên cứu về cấp đa thức và CMG đối xứng, cụ thể: (1) Tìm cấp cực đại của đa thức trên vành bằng việc kiểm tra chiều dài cực đại của các lớp kề cyclic (hay chính là các chu trình). Độ phức tạp O(n). (2) Áp dụng bổ đề 1.4. Tìm các CMG, các đa thức ở vị trí thứ 𝑘 với cấp  gcd , m m k , trong đó 𝑚 là cấp của đa thức sinh của CMG. (3) Áp dụng bổ đề 1.3 để tìm các CMG đối xứng. 9 b) Độ phức tạp thuật toán:  max_ * *O order n N , N là số nhóm nhân cyclic đạt cấp cực đại độc lập (theo bổ đề 1.5 [C5]). c) Thuật toán cải tiến do nghiên cứu sinh đề xuất [C5] INPUT: integer n. OUTPUT: order of all polynomials. 1. Set all   0visited  2. For k from 1 to ( 2 2 n  ) do 2.1. If   1visited k  then continue 2.2. Convert k to polynomial ( )f x 2.3. Set ( ) ( )g x f x 2.4. Set 0count  2.5. While (1) do 2.5.1. Set ( ) ( )* ( )g x g x f x 2.5.2. Convert inversely ( )g x to an integer M 2.5.3.  stored count M 2.5.3. If ( ) ( )g x f x then break the loop End while 2.6. For i from 1 to count 2.6.1.  _poly i s itored 2.6.2. _ _ 2 1 _nopp poly i poly i   2.6.3.    _ / GCD ,ord poly i count i count , and    _ _ _ord opp poly i ord poly i 2.6.4.  _ 1visited poly i  and  _ _ 1visited opp poly i  End for End for Sử dụng cùng cấu hình máy tính để chạy hai thuật toán, kết quả cho thấy thuật toán cải tiến do nghiên cứu sinh đề xuất đã rút ngắn thời gian tính toán một cách đáng kể so với thuật toán vét cạn, đặc biệt khi vành lớn hơn, thuật toán cải tiến có thời gian tính toán ngắn hơn đến hàng nghìn lần và thực hiện được với những vành lớn mà thuật toán vét cạn không thể thực hiện trong cùng một cấu hình máy tính [C5]. 10 2.2.4. Xác suất lựa chọn đa thức có cấp cực đại Nhóm nhân cyclic có cấp cực đại trong các vành đa thức có hai lớp kề cyclic là cơ sở để xây dựng các mã cylic cục bộ có ứng dụng hiệu quả trong viễn thông và trong lĩnh vực bảo mật. Có thể đánh giá khả năng tìm phần tử sinh đạt cấp cực đại trên vành đa thức có hai lớp kề cyclic thông qua tính xác suất chọn theo công thức sau:  1 1 2 1 2 1 n n p n         Số phần tử đạt cấp cực đại (2.7) Số phần tử được lựa chọn với 𝑛 là số phần tử trong nhóm nhân cyclic đơn vị; 12 1n n   là tổng số phần tử (trừ đơn thức và lũy đẳng nuốt);  12 1n   là hàm Phi-Euler. Bảng 2.3 chỉ ra kết quả khảo sát xác suất tìm cấp cực đại của phần tử trên vành đa thức có hai lớp kề cyclic của 35 giá trị đầu tiên của n . Bảng 2.3: Kết quả khảo sát 35 giá trị n TT n p(n) TT n p(n) 1 5 ~0,5 19 179 ~0,663 2 11 ~0,586 20 181 ~0,315 3 13 ~0,42 21 197 ~0,492 4 19 ~0,534 22 211 ~0,377 5 29 ~0,494 23 227 ~0,664 6 37 ~0,378 24 269 ~0,531 7 53 ~0,529 25 293 ~0,530 8 59 ~0,65 26 317 ~0,532 9 61 ~0,35 27 347 ~0,665 10 67 ~0,53 28 349 ~0,445 11 83 ~0,658 29 389 ~0,531 12 101 ~0,45 30 419 ~0,629 13 107 ~0,66 31 421 ~0,318 14 131 ~0,575 32 443 ~0,665 15 139 ~0,559 33 461 ~0,444 16 163 ~0,530 34 467 ~0,665 17 173 ~0,529 35 491 ~0,557 18 173 ~0,529 11 Từ bảng này, có thể nhận thấy xác suất thấp nhất là 0,31 và phần lớn xác suất là trên 0,5. Trong khi chưa có được tiêu chuẩn lựa chọn phần tử sinh có cấp cực đại thì việc đánh giá xác suất lựa chọn phần tử sinh như kết quả ở trên khẳng định rằng khả năng lựa chọn phần tử nguyên thủy (không phải đơn thức) đạt cấp cực đại thông thường đạt trên 50%. Kết quả nghiên cứu này được công bố trong [J2]. 2.3. QUAN HỆ GIỮA NHÓM NHÂN CYCLIC, CẤP SỐ NHÂN CYCLIC VỚI MÃ CYCLIC TRUYỀN THỐNG Một số nghiên cứu trước đây đã dự đoán hoặc cho ví dụ trong một số trường hợp riêng về một quan hệ giữa nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống, tuy nhiên cho đến hiện tại vẫn chưa có công trình nghiên cứu nào đưa ra chứng minh toán học chặt chẽ cho trường hợp tổng quát về mối quan hệ này. Trong nội dung này của luận án, nghiên cứu sinh sẽ đề xuất một cách chứng minh toán học chặt chẽ cho mối quan hệ này trong trường hợp tổng quát và kết quả thực nghiệm trên công cụ mô phỏng mối quan hệ giữa nhóm nhân cyclic, cấp số nhân cyclic trên vành đa thức với mã cyclic truyền thống. 2.3.1. Cơ sở toán học 2.3.1.1. Quan hệ giữa phép nhân và ánh xạ tuyến tính trên nR . 2.3.1.2. Một tính chất của tích vô hướng 2.3.2. Sự tương đương của nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống Bổ đề 2.4: Mã cyclic cục bộ xây dựng từ một cấp số nhân cyclic cũng là một mã cyclic truyền thống. Mã cyclic này được xây dựng trên vành đa thức có bậc là cấp của cấp số nhân cyclic trong phân hoạch của vành đa thức xây dựng cấp số nhân cyclic [J4]. Việc chứng mình hoàn chỉnh bổ đề 2.4 đưa đến khẳng định rằng mã cyclic cục bộ xây dựng từ cấp số nhân cyclic là một mã cyclic, từ đây có thể mở ra một phương án mới để xây dựng các lớp mã cyclic. Với phương án tiếp cận này, việc xây dựng các mã cyclic (nhất là với các mã cyclic ở trên các vành lớn) trở nên đơn giản hơn, ta chỉ cần khảo sát các cấp số nhân cyclic trên các vành nhỏ cũng có thể xây dựng được các mã cyclic ở trên các vành lớn, trong khi đối với các vành lớn (số mũ 𝑛 lớn), việc phân tích giá trị (𝑥𝑛 + 1) ra thành các đa thức bất khả quy cũng là một trở ngại cho việc xây dựng mã cyclic. 12 2.3.3. Thuật toán xác định nhóm nhân cyclic tương đương mã cyclic truyền thống Từ kết quả bổ đề 2.4, khi 1  thì cấp số nhân cyclic tương đương nhóm nhân cyclic, do đó có thể nhận định rằng mã LCC xây dựng trên nhóm nhân cyclic cũng tương đương với mã cyclic truyền thống. Phần này sẽ trình bày kết quả khảo sát và đánh giá về sự tương đương giữa mã LCC xây dựng trên nhóm nhân cyclic và mã cyclic truyền thống. Thuật toán xác định mã cyclic truyền thống tương đương [C3] VÀO:    2[ ] / 1nxa Z xx   RA: Mã cyclic truyền thống tương đương với CMG { ( ), 1,2,..., }iA a x i m  Bước 1: - Xây dựng { ( ), 1,2,..., }iA a x i m  . - Đặt   n ord a x - Lập ma trận mã LCC từ các phần tử của CMG A . - Sử dụng thuật toán Gauss-Jordan để chuyển ma trận lập được ở trên về dạng ma trận hệ thống. - Loại bỏ các hàng bằng 0 (nếu có) của ma trận mã, được ma trận sinh  ,G n k . Bước 2: - Chuyển đổi ma trận sinh  ,G n k về dạng các phần tử trong nhóm - Đặt       2& ; / ( 1) nh x A k k h x Z x   - Tính     * 1nx g x h x         - Từ đa thức sinh  g x , được ma trận mã tương đương với mã cyclic truyền thống. Nghiên cứu sinh đã xây dựng chương trình phần mềm và chạy thuật toán xác định các mã tương đương được trình bày trong [C3] và phụ lục của luận án. 13 2.4. MỘT CÁCH PHÂN LOẠI MÃ TUYẾN TÍNH MỚI Từ quan điểm xây dựng mã cyclic và LCC, có thể thực hiện mô tả mã cyclic theo quan điểm xây dựng mã LCC dựa trên phân hoạch vành đa thức. Nghiên cứu các mã LCC trong mối quan hệ với mã cyclic nói riêng và trong hệ thống mã tuyến tính xây dựng trên các cấu trúc đại số nói chung, với các dạng phân hoạch khác nhau có thể cho ra các loại mã sửa lỗi khác nhau, hệ thống phân loại các mã tuyến tính xây dựng trên các cấu trúc đại số được trình bày trong hình 2.3 [C4]. Mã tuyến tính Không có cấu trúc Có cấu trúc Vành số Mã cyclic AN Vành đa thức Z2[x]/x n+1 Phân hoạch vành theo CMG Vành các lớp liên hợp Vành đồng dư Trên một vành Trên hai vành Vành và vành ước của vành Hai vành bất kỳ LCC hỗn hợp Phân hoạch cực tiểu Phân hoạch chuẩn Phân hoạch cực đại LCC đa nhịp LCC đơn nhịp LCC Mã cyclic nhịp x   modi xxI h Vành ma trận Ma trận Cauchy Ma trận Vandermon Mã cyclic theo Ideal I= Mã Goppa Mã tuyến tính ngẫu nhiên Mã BCH Mã tựa LCC n lẻ Mã cyclic với nhịp đa thức n chẵn n bất kỳ Hình 2.3. Sơ đồ phân loại mã tuyến tính dựa trên cấu trúc đại số và mã LCC [C4] 2.5. KẾT LUẬN CHƯƠNG Chương 2 đã trình bày kết quả nghiên cứu mới góp phần hoàn thiện lý thuyết về mã cyclic. Các kết quả đã được công bố trong các công trình [J2], [J3], [J4], [J5], [C3], [C5] tập trung vào hai nội dung chính: 14 1) Kiến thiết các nhóm nhân cyclic trên vành đa thức thông qua việc đề xuất phương pháp xác định cấp của đa thức và đa thức đạt cấp cực đại, đồng thời chứng minh hoàn chỉnh một số bổ đề quan trọng, cụ thể: (a) Đề xuất phương pháp xác định cấp của đa thức là tích các đa thức trên vành đa thức với đóng góp quan trọng nhất là đề xuất và chứng minh hoàn chỉnh bổ đề 2.2 [J5]; (b) Đề xuất phương pháp xác định cấp của nhị thức trên vành đa thức với đóng góp là đề xuất và chứng minh hoàn chỉnh bổ đề 2.3 [J3], [J5]; (c) Đề xuất thuật toán cải tiến để tìm và liệt kê cấp của đa thức trên vành đa thức [C5]; (d) Đánh giá xác suất tìm phần tử có cấp cực đại trên vành đa thức có hai lớp kề cyclic [J2]. 2) Chứng minh sự tương đương giữa các nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống, với việc trình bày một chứng minh về lý thuyết (bổ đề 2.4), xây dựng thuật toán (thuật toán 2.4), sau đó tiến hành khảo sát, đánh giá và xây dựng được một phụ lục minh chứng cho tính tương đương này [J4], [C3]. Ở cuối chương, Luận án đã trình bày và thảo luận một sơ đồ phân loại các mã tuyến tính dựa trên cấu trúc đại số và mã cyclic cục bộ, góp phần khẳng định mối quan hệ giữa mã cyclic với mã cyclic cục bộ và vai trò của mã LCC trong hệ thống mã tuyến tính, mã sửa lỗi [C4]. CHƯƠNG 3 ỨNG DỤNG NHÓM NHÂN CYCLIC, CẤP SỐ NHÂN CYCLIC Tóm tắt: Các kết quả đạt được trong chương 2 là cơ sở để tiếp tục nghiên cứu ứng dụng của nhóm nhân cyclic, cấp số nhân cyclic trong mã sửa lỗi và mật mã. Một đặc điểm nổi bật của các bộ mã cyclic xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic là có độ dài thay đổi được có khả năng ứng dụng trong LTE, mã mạng. Trong số các nhóm nhân trên một vành đa thức thì nhóm nhân có cấp cực đại có độ ngẫu nhiên của các phần tử cao nhất do đó có thể sử dụng các phần tử có cấp cao nhất trong nhóm nhân cấp cực đại trên vành đa thức làm khóa cho một số hệ mật. Trong chương này, luận án sẽ trình bày phương pháp xây dựng mã cyclic, tiếp đến đề xuất một số mã cyclic tốt xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic gồm phương pháp tìm mã cyclic tốt, danh sách một số mã cyclic tốt được đề xuất, mô phỏng đánh giá bộ mã, đồng thời đề xuất phương pháp xây dựng bộ mã trên cấu kiện phần 15 cứng FPGA. Nội dung cuối, luận án trình bày ứng dụng của nhóm nhân cyclic, cấp số nhân cyclic làm khóa cho một số hệ mật. 3.1. PHƯƠNG PHÁP XÂY DỰNG MÃ CYCLIC 3.1.1. Phương pháp xây dựng mạch mã hóa Trên cơ sở đã xác định được các nhóm nhân sinh, sẽ tạo được cấp số nhân cyclic tương đương với lớp kề mới, phần tử sinh của lớp kề (trưởng lớp kề) tương ứng số hạng đầu của cấp số nhân cyclic. Nếu gắn dấu thông tin cho nhóm nhân sinh, ta sẽ tạo được mã LCC tương ứng với nhóm nhân đó. Có hai cách chọn nhóm nhân sinh: + Cách thứ nhất: Chọn nhóm nhân đơn vị I, các dấu thông tin được gắn vào nhóm nhân đơn vị I để tạo mã. + Cách thứ hai: Chọn nhóm nhân sinh là nhóm nhân cyclic bất kỳ. Chọn phần tử đầu tiên ( )a x nhân với nhóm nhân sinh đó sẽ tạo ra được cấp số nhân cyclic tương ứng với một lớp kề tạo mã. 3.1.2. Phương pháp xây dựng mạch giải hóa Có nhiều phương pháp giải mã cho mã cyclic và LCC, trong số đó giải mã ngưỡng là một phương pháp khá hiệu quả và có sơ đồ giải mã đơn giản. Các phương pháp giải mã ngưỡng bao gồm: Giải mã ngưỡng theo đa số (MTD) các tổng kiểm tra; Giải mã ngưỡng theo đa số 1 biểu quyết (MTD + 1); giải mã ngưỡng theo đa số 2 biểu quyết (MTD + 2). Các phương pháp giải mã ngưỡng đều sử dụng các OCS, hoặc các OACS, hoặc CS  liên hệ. 3.2. ĐỀ XUẤT MỘT SỐ MÃ CYCLIC TỐT TRÊN VÀNH ĐA THỨC 3.2.1. Phương pháp tìm mã cyclic tốt Phần này trình bày phương pháp tìm mã cyclic (n,k,d) tốt phù hợp theo các tiêu chí đánh giá đề cập trong chương 1. Các kết quả nghiên cứu liên quan đến mã cyclic xây dựng từ nhóm nhân, cấp số nhân cyclic. 3.2.1.1. Mã cyclic tối ưu xây dựng từ nhóm nhân, cấp số nhân cyclic Định lý 3.1: Mã cyclic (2𝑘 − 2, 𝑘) trên vành đa thức 𝑍2[𝑥]/(𝑥 𝑘 + 1) sử dụng tất cả đa thức khác không (trừ đa thức 𝑒0(𝑥) = ∑ 𝑥 𝑖𝑘−1 𝑖=0 ) làm dấu mã là mã tối ưu đạt giới hạn Griesmer và thỏa mãn giới hạn Plotkin, có khoảng cách mã 𝑑0 = 2 𝑘−1 − 1 [J6]. Định lý 3.2: Mã cyclic (2𝑘−1 − 1, 𝑘) trên vành đa thức 𝑍2[𝑥]/(𝑥 𝑘 + 1) với 𝑘 lẻ và sử dụng tất cả đa thức trọng số lẻ (trừ đa 16 thức 𝑒0(𝑥) = ∑ 𝑥 𝑖𝑘−1 𝑖=0 ) làm dấu mã là mã tối ưu đạt giới hạn Griesmer và thỏa mãn giới hạn Plotkin, có khoảng cách 𝑑0 = 2 𝑘−2 − 1 [J6]. Đối với mã cyclic xây dựng từ các nhóm nhân cyclic thì có thể xây dựng các bộ mã này như sau: + Nếu cấp cực đại của các đa thức thuộc vành 𝑍2/(𝑥 𝑘 + 1) bằng 2𝑘−1 − 1 thì chọn đa thức có cấp cực đại làm phần tử sinh của bộ mã. + Nếu cấp cực đại của các đa thức thuộc vành 𝑍2/(𝑥 𝑘 + 1) không nhỏ hơn 2𝑘−1 − 1 thì chọn đa thức thuộc vành lớn hơn (vành 𝑍2/(𝑥 𝑝 + 1), với 𝑝 > 𝑘) và có cấp bằng với 2𝑘−1 − 1 sau đó hạ bậc đa thức theo ℎ(𝑥) thì được đa thức mới có thể chọn làm phần tử sinh của bộ mã. Việc hạ bậc đa thức theo ℎ(𝑥) như vậy là trường hợp phân hoạch hỗn hợp trên hai vành đa thức bất kỳ. Xét 2 vành 1px  và 1kx  với p k nếu trên vành 1px  ta tìm được đa thức ( )h x thỏa mãn điều kiện: ( )h x là tích của một số đa thức bất khả quy và deg ( )h x k thì ta có thể thực hiện được phân hoạch hỗn hợp trên hai vành này [J6]. Dựa trên kết quả hai định lý 3.1, 3.2 cùng với phân tích ℎ(𝑥), có thể nhận thấy rằng luôn có thể xây dựng được các bộ cyclic mã tối ưu trên các vành đa thức từ các cấp số nhân (hay lớp kề) cyclic. 3.2.1.2. Mã cyclic tốt xây dựng từ cấp số nhân cyclic Các mã cyclic tối ưu (𝑛, 𝑘, 𝑑) được nghiên cứu và đề xuất ở trên có ưu điểm là sửa lỗi tốt (𝑑 lớn), xây dựng bộ mã dễ dàng, tuy nhiên tồn tại một nhược điểm lớn là hiệu suất mã (𝑘/𝑛) thường khá nhỏ, do đó nghiên cứu sinh đề xuất phương pháp tìm mã cyclic tốt xây dựng từ các cấp số nhân/ lớp kề cyclic với các giá trị (𝑛, 𝑘, 𝑑) phù hợp, đặc biệt là đề xuất các mã tốt xây dựng từ 3 lớp kề cyclic trên vành. Để tìm mã cyclic tốt xây dựng trên 3 lớp kề cyclic sử dụng phương pháp giải mã ngưỡng, ta thực hiện theo các bước sau đây [J6]: Bước 1: + Cho giá trị 𝑘 của vành đa thức 𝑍2/(𝑥 𝑘 + 1). + Lập phân hoạch cho vành đa thức, xác định số lớp kề 𝑚 (số lượng lớp kề trong vành) + Cho 𝑖 = 2 Bước 2: + Gán 𝑗 = 𝑖 + 1 Bước 3: + Lập mã gồm 3 lớp kề {1, 𝑖, 𝑗} 17 + Xác định giá trị 𝑛 trong bộ mã (𝑛, 𝑘, 𝑑) , trong đó 𝑛 là tổng số phần tử của 3 lớp kề được chọn (cũng là độ dài từ mã). + Tính tổng kiểm tra của bộ mã theo cả 3 trường hợp CS trực giao, CS có khả năng trực giao, CS  liên hệ, sau đó lưu lại số CS của bộ mã ứng với mỗi trường hợp. Từ số tổng kiểm tra sẽ tính được khoảng cách Hamming 𝑑. + Nếu 𝑗 = 𝑚 thì chuyển sang bước 4, nếu 𝑗 < 𝑚 thì tăng 𝑗 và lặp lại bước 3. Bước 4: + Nếu 𝑖 = 𝑚 − 1 thì chuyển sang bước 5, nếu 𝑖 < 𝑚 − 1 thì tăng 𝑖 và lặp lại bước 2. Bước 5: Tính toán bộ tham số (𝑛, 𝑘, 𝑑) ứng với các bộ mã, so sánh với các giới hạn tối ưu. Liệt kê bộ mã (𝑛, 𝑘, 𝑑) tốt nhất thu được. j = i + 1; Lập hệ tổng kiểm tra của bộ mã j = m N Y Bắt đầu Cho giá trị của k Lập phân hoạch cho vành đa thức Cho i = 2 Lập mã gồm 3 lớp kề {1, i, j} Xác định n j = j + 1 i = i + 1 i = m - 1 N Y Liệt kê bộ mã (n, k, d) tốt Kết thúc Hình 3.3: Lưu đồ thuật toán tìm bộ mã cyclic tốt xây dựng từ cấp số nhân cyclic [J6] 18 Từ các bước trên có thể xây dựng được lưu đồ thuật tìm các bộ mã cyclic tốt theo lưu đồ thuật toán như trên hình 3.3. Trên cơ sở thuật toán nghiên cứu sinh đã viết chương trình và xây dựng được một bảng kết quả một số mã cyclic tốt đ