Tóm tắt Luận án tiến sĩ Kỹ thuật: Nhóm nhân cyclic và mã cyclic trên vành đa thức

Chia sẻ: Trần Văn Yan | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

16
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích cơ bản của luận án này là phương pháp kiến thiết nhóm nhân cyclic có cấp cực đại trên vành đa thức. Đề xuất ứng dụng của nhóm nhân cyclic, cấp số nhân cyclic để tìm một số bộ mã cyclic tốt, hay ứng dụng trong các hệ mật.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án tiến sĩ Kỹ thuật: Nhóm nhân cyclic và mã cyclic trên vành đa thức

BỘ THÔNG TIN VÀ TRUYỀN THÔNG HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG NGUYỄN TRUNG HIẾU NHÓM NHÂN CYCLIC VÀ MÃ CYCLIC TRÊN VÀNH ĐA THỨC CHUYÊN NGÀNH: KỸ THUẬT ĐIỆN TỬ MÃ SỐ: 9520203 (mã cũ 62.52.02.03) TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT HÀ NỘI - 2017
Công trình được hoàn thành tại: Học viện Công nghệ Bưu chính Viễn thông Người hướng dẫn khoa học: GS.TS. Nguyễn Bình TS. Nguyễn Ngọc Minh Phản biện 1: PGS.TS. Đỗ Quốc Trinh Phản biện 2: PGS.TS. Nguyễn Hiếu Minh Phản biện 3: PGS.TS. Đặng Văn Chuyết Luận án sẽ được bảo vệ trước hội đồng chấm luận văn tại: Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... năm …… Có thể tìm hiểu luận án tại: Thư viện Quốc gia Việt Nam Thư viện Học viện Công nghệ Bưu chính Viễn thông
i MỞ ĐẦU Lý do nghiên cứu Việc nghiên cứu truyền thống về mã cyclic đã khá hoàn chỉnh, tuy nhiên loại mã này có nhược điểm là số lượng từ mã được tạo ra hạn chế, độ dài của mã chỉ cố định ở một số giá trị cụ thể. Trong những năm trở lại đây một phương pháp khác để xây dựng mã cyclic (gọi là mã cyclic cục bộ) được nghiên cứu dựa trên phân hoạch vành đa thức. Về mặt lý thuyết có thể tồn tại mối quan hệ giữa mã cyclic và cyclic cục bộ, điều đó thôi thúc nghiên cứu sinh nghiên cứu sâu hơn lý thuyết về mã cyclic cục bộ (mã cyclic được xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic), tìm hiểu, chứng minh mối quan hệ có thể tồn tại giữa mã cyclic và mã cyclic cục bộ. Mục đích nghiên cứu Mục đích chính của luận án là góp phần hoàn thiện lý thuyết và thực nghiệm về nhóm nhân cyclic và mã cyclic trên các vành đa thức, khảo sát và chứng minh mối quan hệ giữa mã cyclic cục bộ và mã cyclic truyền thống. Trên cơ sở kết quả nghiên cứu lý thuyết đạt được sẽ đề xuất một số ứng dụng có thể về mã sửa lỗi và mật mã trong các hệ thống truyền thông. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu của luận án là các đa thức, nhóm nhân cyclic, cấp số nhân cyclic và mã cyclic trên vành đa thức. Phạm vi nghiên cứu của luận án này được giới hạn trong việc nghiên cứu 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, cấp của đa thức và phương pháp xây dựng nhóm nhân cyclic có cấp cực đại trên vành đa thức, trên cơ sở đó có thể đề xuất một số mã cyclic tốt và phương pháp hiện thực hóa các mã cyclic trên FPGA. Phương pháp và công cụ nghiên cứu Phương pháp nghiên cứu của đề tài là phân tích và tổng hợp dựa vào các công cụ toán học, đặc biệt là đại số, lý thuyết mã hóa, lý thuyết xác suất,... Luận án sử dụng các công cụ toán học, kết hợp với việc tính toán, mô phỏng trên máy tính và các chương trình phần mềm xử lý (C++, Matlab, VHDL, Excel).
ii Ý nghĩa khoa học và thực tiễn của đề tài Những kết quả trong luận án này góp phần phát triển hoàn thiện lý thuyết mã cyclic, mã cyclic cục bộ nói riêng và lý thuyết mã sửa lỗi nói chung. Các đóng góp chính của Luận án: - Kiến thiết các nhóm nhân cyclic có cấp cực đại trên vành đa thức thông qua việc đề xuất phương pháp xác định đa thức có cấp cực đại. - Chứng minh sự tương đương giữa nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống. - Đề xuất một số bộ mã cyclic tốt xây dựng trên vành đa thức. Cấu trúc của Luận án Nội dung luận án bao gồm phần mở đầu, kết luận và ba chương nội dung. Trong đó, Chương 1 trình bày tổng quan vấn đề nghiên cứu, lý thuyết cơ bản về vành đa thức, mã cyclic làm cơ sở cho các nội dung nghiên cứu của luận án. Trong Chương 2, luận án tập trung trình bày các kết quả nghiên cứu mới và hai đóng góp quan trọng của Luận án là đề xuất phương pháp kiến thiết các nhóm nhân cyclic có cấp cực đại thông qua việc xác định cấp của đa thức với nhiều hướng tiếp cận; chứng minh mối quan hệ tương đương giữa mã cyclic truyền thống với mã cyclic xây dựng trên nhóm nhân, cấp số nhân trên vành đa thức [J2], [J3], [J4], [J5], [C3], [C4], [C5]. Ở Chương 3, Luận án trình bày phương pháp tìm mã cyclic tốt và danh sách một số mã cyclic tốt được đề xuất, cũng như mô phỏng đánh giá bộ mã, đề xuất phương pháp xây dựng bộ mã trên cấu kiện phần cứng FPGA, ở cuối chương luận án trình bày ứng dụng của nhóm nhân cyclic, cấp số nhân cyclic trong việc làm khóa một số hệ mật [J1], [J6], [C1], [C2].
1 CHƯƠNG 1 TỔNG QUAN CÁC VẤN ĐỀ CẦN NGHIÊN CỨU Tóm tắt: Nội dung của chương trình bày lý thuyết tổng quan về vành đa thức, nhóm nhân cyclic, cấp số nhân cyclic và mã cyclic. Các tiêu chuẩn đánh giá mã sửa lỗi cũng được giới thiệu trong chương này. Chương này cũng sẽ tập trung khảo sát các nghiên cứu liên quan đến mã cyclic để từ đó tìm ra các hạn chế của các nghiên cứu trước đây và đề xuất hướng nghiên cứu, phạm vi nghiên cứu và phương thức tiếp cận của luận án. 1.1. GIỚI THIỆU CHUNG Phần này trình bày tổng quan về lịch sử phát triển của lý thuyết mã hoá, mã sửa lỗi, mã tuyến tính, mã cyclic và đề cập đến mã cyclic xây dựng trên vành đa thức. 1.2. VÀNH ĐA THỨC Phần này đề cập đến các khái niệm cơ bản về vành đa thức, phép tính trên vành đa thức, đa thức bất khả quy, đa thức đối xứng, vành đa thức có hai lớp kề cyclic. Tiếp đến là các nội dung liên quan đến chu trình, lũy đẳng, đặc biệt bổ đề 1.2 đề cập đến tính chất và hệ quả về lũy đẳng nuốt được sử dụng cho các chứng minh kết quả chính của luận án. 1.3. MÃ TUYẾN TÍNH Phần này đưa ra khái niệm về mã tuyến tính, tiếp theo trình bày về mã cyclic, một số mã có tính chất tương tự có thể xây dựng trên vành đa thức, và một số tiêu chuẩn đánh giá mã tuyến tính phổ biến. 1.3.1. Mã cyclic truyền thống 1.3.2. Một số mã tuyến tính khác 1.3.3. Một số tiêu chuẩn đánh giá mã tuyến tính 1.4. PHÂN HOẠCH VÀNH ĐA THỨC VÀ MÃ CYCLIC CỤC BỘ Phần này trình bày về lý thuyết về nhóm nhân cyclic, nhóm nhân cyclic đối xứng, cấp của đa thức và phân bố đa thức theo cấp trong nhóm nhân cyclic. Tiếp đến là các nội dung liên quan đến cấp số nhân cyclic, phân hoạch vành đa thức và mã cyclic cục bộ. 1.4.1. Nhóm nhân cyclic Nhóm nhân cyclic trong vành đa thức là tập hợp các phần tử 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ó
2 nhiều nhóm nhân mỗi nhóm nhân có thể gồm 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  { ,  2 ,  3 ...,  m } (1.16) Bổ đề 1.3: Xét a  x  là một phần tử sinh của nhóm nhân cyclic A, a  x  là phần tử sinh của nhóm nhân cyclic A ( A được gọi là đối xứng của nhóm nhân A). Ta có:  A  a i  x  mod  x n  1  A  a  x  mod  x i n  1 (1.19) A  A ; a i  x   ai  x  Cấp của đa thức a ( x )  2 [ x ] / ( x n  1) (ký hiệu ord a( x) ) là số nguyên dương 𝑚 nhỏ nhất thỏa mãn:  a ( x)   a( x) mod ( x n  1) hoặc  a( x)   e( x) mod ( x n  1) (1.21) m 1 m Định lý 1.2: Xét vành đa thức Z 2 [ x ] / x n  1 với x n  1   fi ( x) trong đó f i ( x ) là các đa thức bất khả quy, cấp cực đại của một đa thức a( x) nào đó được xác định như sau: - Nếu 𝑛 lẻ thì max ord (a( x))  2m  1 . - Nếu 𝑛 chẵn, có dạng n  2s (2k  1) thì max ord (a( x))  2s (2m 1) . Trong đó m  max deg fi ( x) . Bổ đề 1.4 trình bày về phân bố đa thức theo cấp trong nhóm nhân cyclic, trong khi bổ đề 1.5 nói về số đa thức đạt cấp cực đại trên vành. 1.4.2. Cấp số nhân cyclic 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: A( a ,q )  a ( x), a( x)q( x), a( x) q 2 ( x),..., a( x) q m 1 ( x) (1.23) 1.4.3. 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
3 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. Dựa vào các lớp kề này ta có thể tạo được mã LCC và các mã cyclic khác nhau. Trong vành đa thức, số phân hoạch là khá lớn nên có thể xây dựng được nhiều mã cyclic có đặc tính sửa lỗi tốt. Các kiểu phân hoạch vành đa thức phổ biến: a) Phân hoạch chuẩn b) Phân hoạch cực đại c) Phân hoạch cực tiểu d) Phân hoạch vành thành các cấp số nhân có cùng trọng số e) Phân hoạch vành thành các phần tử có cùng tính chẵn lẻ của trọng số f) Phân hoạch vành thành các cấp số nhân theo modulo h(x) 1.4.4. Mã cyclic cục bộ trên vành đa thức Mã cyclic cục bộ là một mã tuyến tính có các dấu mã là một tập con không trống tuỳ ý các lớp kề trong phân hoạch của vành đa thức theo một nhóm nhân cyclic A . Nhận xét: - Nếu chỉ chọn 1 lớp kề, khi đó mã LCC trở thành mã cyclic. - Nếu các lớp kề được chọn có chứa nhóm nhân cyclic đơn vị I   xi , i  1, 2,3... thì ta có mã LCC hệ thống. Tập các trưởng lớp kề tạo mã sẽ mô tả đầy đủ mã LCC. Có hai cách biểu diễn mã cyclic cục bộ phổ biến là: a) Biểu diễn theo trưởng lớp kề; b) Biểu diễn theo ma trận sinh. Hai lớp mã LCC phổ biến là: a) Mã cyclic cục bộ tự trực giao (OLCC); b) Mã LCC có khả năng trực giao (OALCC). 1.5. HƯỚNG NGHIÊN CỨU CỦA LUẬN ÁN VÀ MỘT SỐ KẾT QUẢ LIÊN QUAN Trên thế giới, việc nghiên cứu cấu trúc đại số cho các cấu trúc mã hiện nay vẫn đang được nghiên cứu và hoàn thiện như mã LDPC, mã Turbo nhằm mục đích tối ưu hóa các mã kênh, mã truyền tin trong các mạng thông tin di động thế hệ mới. Đối với mã cyclic, một số hướng
4 nghiên cứu trên thế giới hiện nay đã khá hoàn thiện và hiện đang xem xét một số giới hạn của mã cyclic, đánh giá trọng số của mã cyclic, đề xuất phương án giải mã tối ưu cho mã cyclic. Một số nghiên cứu đề cập đến mã tuyến tính và đặc tính của các đa thức sinh dựa trên cấu trúc trellis, đề xuất xây dựng mã khác dựa trên mã cyclic. Hiện nay các công trình nghiên cứu đề cập đến mã cyclic đều đang tìm thêm các ứng dụng dựa trên tính chất dịch vòng của mã cyclic ví dụ tính các chuỗi nhảy tần tối ưu trong thông tin di động, xây dựng cấu trúc đại số mới để hình thành mã quasi cyclic, hay quasi cyclic LDPC, hiện thực hóa các mã cyclic trên các cấu kiện phần cứng. Tuy nhiên, việc nghiên cứu các mã cyclic còn chưa chặt chẽ và mang tính tổng thể đối với vành đa thức. Ở Việt Nam, vào năm 1987 đã bắt đầu một hướng nghiên cứu mới về mã sửa lỗi đó là mã cyclic cục bộ (LCC) được thực hiện trênh vành số. Tuy nhiê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. k Bổ đề 2.1: Xét đa thức g ( x)   fi ( x) ; trong đó fi ( x) là các đa i 1 thức có cấp tương ứng là 𝑚𝑖 . Khi đó, cấp của g ( x) thỏa mãn [J5]: ord  g ( x)  lcm  m1 , m2 ,..., mk  (2.1) Bổ đề 2.2: Xét f1 ( x), f 2 ( x)  2 [ x] / ( xn  1) . Cấp của đa thức g ( x)  f1 ( x). f 2 ( x) xác định như sau [J5]: 1) Trường hợp 1: Xét hai đa thức f1 ( x)  a i ( x) và f 2 ( x )  a j ( x ) (hoặc f 2 ( x )  a j ( x ) ), a( x)  CMG A cấp 𝑚 thì m ord  f1 ( x). f 2 ( x)   (2.2) gcd  m, (i  j )  2) Trường hợp 2: Nếu f1 ( x)  CMG A1 và f 2 ( x)  CMG A 2 , với A1  A 2 và không đối xứng nhau, cấp tương ứng của A1 , A2 là m1 , m2 ord  f1 ( x). f 2 ( x)   lcm  m1 , m2  (2.3)
7 Đặc biệt nếu gcd  m1 , m2   1 , thì ord  f1 ( x). f 2 ( x)   m1 .m2 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  x j trên 2 [ x ] / ( x n  1) được xác định [J3]: ord (1  x j ) | (2mi  1) víi j  Ci (2.5) Bổ đề 2.3: Trên vành đa thức 2 [ x ] / ( x  1) [J5]. n + Các nhị thức (1  x ) với j  C1 là các nhị thức có cấp lớn nhất. j + 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à order  1  3. Lấy g  x   XOR g  x  , shift  g  x  ,1  4. So sánh g  x  với a  x  : 4.1. Nếu g  x   a  x  thì order  order  1 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 a( x)  1  x  . f ( x), (với điều kiện gcd  ord  f ( x)  , ord 1  x    1 ). 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ứ 𝑘 m với cấp , trong đó 𝑚 là cấp của đa thức sinh của CMG. gcd  m, k  (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: O  max_ 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 visited    0 2. For k from 1 to ( 2n  2 ) do 2.1. If visited  k   1 then continue 2.2. Convert k to polynomial f ( x) 2.3. Set g ( x)  f ( x) 2.4. Set count  0 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  stored i  2.6.2. opp _ poly _ i  2n  1  poly _ i 2.6.3. ord  poly _ i   count / GCD  i , count  , and ord  opp _ poly _ i   ord  poly _ i  2.6.4. visited  poly _ i   1 and visited  opp _ poly _ i   1 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: Số phần tử đạt cấp cực đại   2n 1  1 p  (2.7) 2n 1  1  n Số phần tử được lựa chọn với 𝑛 là số phần tử trong nhóm nhân cyclic đơn vị; 2n 1  1  n là tổng số phần tử (trừ đơn thức và lũy đẳng nuốt);   2n 1  1 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 Rn . 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: a  x   Z 2 [x] /  x n  1 RA: Mã cyclic truyền thống tương đương với CMG A  {ai ( x), i  1, 2,..., m} Bước 1: - Xây dựng A  {ai ( x), i  1, 2,..., 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 h  x   A k  & k ; h  x   Z 2 / ( x n  1) *  xn  1  - Tính 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ó cấu trúc Vành số Mã cyclic AN cấu trúc Mã tuyến Vành đa thức n chẵn Vành các lớp tính ngẫu Vành ma trận Z2[x]/xn+1 liên hợp nhiên n lẻ n bất kỳ Ma trận Ma trận Vành đồng Phân hoạch vành Cauchy Vandermon LCC dư theo CMG Mã Mã BCH Goppa Trên Trên Mã cyclic một hai theo Ideal vành vành I= Phân hoạch Phân hoạch Phân hoạch Vành và Hai vành cực tiểu chuẩn cực đại vành ước bất kỳ của vành LCC đa nhịp LCC hỗn Mã tựa hợp LCC LCC đơn nhịp   I  xi mod h  x  Mã cyclic với Mã cyclic nhịp x nhịp đa thức 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 𝑘−1 2 − 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 x p  1 và x k  1 với p  k nếu trên vành x p  1 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, 𝑖, 𝑗}