Các mã cyclic trấn vành Mersenne

Bài báo này trình bày một số tính chất của các nhóm nhân cyclic trên vành Mersenne. Các nhóm nhân cyclic này là cơ sở cho việc xây dựng các mã cyclic cục bộ. Có thể thấy rằng tất cả các nhóm nhân cyclic trên vành Mersenne đều tương đương với tất cả các mã cyclic trên vành này và các vành ước của nó.
Nội dung trích xuất từ tài liệu:
Các mã cyclic trấn vành MersenneKỹ thuật điện tử & Khoa học máy tính C¸c m· CYCLIC TRÊN Vµnh MERSENNE NGUYỄN VĂN TRUNG Tóm tắt: Bài báo này trình bày một số tính chất của các nhóm nhân cyclic trên vành Mersenne. Các nhóm nhân cyclic này là cơ sở cho việc xây dựng các mã cyclic cục bộ. Có thể thấy rằng tất cả các nhóm nhân cyclic trên vành Mersenne đều tương đương với tất cả các mã cyclic trên vành này và các vành ước của nó.Từ khóa: Cyclic, Nhóm nhân Cyclic, Cyclic cục bộ. 1. ĐẶT VẤN ĐỀ Lý thuyết mã hóa đã được phát triển từ lâu và được ứng dụng rộng rãi trong nhiều lĩnh vực củacuộc sống, đặc biệt là lĩnh vực thông tin. Lý thuyết mã hóa phát triển theo ba hướng cơ bản là mãnguồn, mã kênh và mật mã [1,2]. Đa số các mã khống chế sai thường xây dựng theo hướng kiếnthiết cho định lý thứ hai của Shannon với hướng chủ đạo là xây dựng các mã trên các cấu trúc đạisố theo quan điểm mã là một tập con có cấu trúc trong một cấu trúc đại số nào đó [3]. Thành tựunổi bật trong hướng này là mã cyclic. Mã cyclic là mã khối tuyến tính được xây dựng trên các Ideal của vành đa thức, mỗi từ mã làmột phần tử của Ideal trên vành đa thức đó. Với mã cyclic cục bộ, mỗi dấu mã là một phần tử củamột bộ phận có cấu trúc trong vành. Có thể coi mã cyclic truyền thống là một lớp con của mãcyclic cục bộ hay mã cyclic truyền thống là một dạng đặc biệt của mã cyclic cục bộ[9]. Bài báo này trình bày về một số tính chất của mã cyclic cục bộ xây dựng trên vành Mersenne,dựa trên những kiến thức nền tảng về cấu trúc đại số và các kết quả nghiên cứu trước đó về mãcyclic cục bộ. 2. CẤP CỦA NHÓM NHÂN CYCLIC TRÊN VÀNH MERSENNE Định nghĩa 1: Vành đa thức Mersenne x n  1 là vành đa thức có giá trị n thỏa mãn: n  2m  1 . Định nghĩa 2: Cho Sn   n 0,1,..n  1 , n lẻ Lớp kề cyclic Ci theo modulo trên GF  2  là tập hợp sau:  Ci  i.2 j mod n, j  0,1,..  Ci  i.2 , i.4 ,..i.2 j j mi  1 mi Trong đó: i.2  i mod n Ta có C i  Sn , Ci  C j   . Như vậy tập các lớp kề Ci tạo nên một phân hoạch của  n: Ci  mi ;  mi  n i Nhận xét: Ta có phân tích: x n  1   f  x i i  fi  x  : đa thức bất khả quy  Số các đa thức bất khả quy fi  x  bằng số các Ci trong phân hoạch S n  deg fi  x   Ci  mi . Ví dụ 1:44 N. V. Trung, “Các mã cyclic trên vành Mersenne.”Nghiên cứu khoa học công nghệ n  5: C0  0 C1  1, 2, 4,3  x 5  1  1  x  1  x  x 2  x 3  x 4  n 7: C0  0 C1  1, 2, 4 C3  3, 6,5   x 7  1  1  x  1  x  x 3 1  x 2  x 3  n  15 : C0  0 C1  1, 2, 4,8 C3  3, 6,12,9 C5  5,10 C7  7,14,13,11     x15  1  1  x  1  x  x 2 1  x 3  x 4 1  x  x 4 1  x  x 2  x 3  x 4  Định lý 1 [4]: Trong vành Mersenne n  2 m  1 đa thức x n  1 được phân tích thành tích củatất cả các đa thức bất khả quy có bậc m và ước của m Định nghĩa 3: Nhóm nhân cyclic A với phần tử sinh a  x  trên vành đa thức   2 [ x ] / x n  1 được thiết lập theo công thức:  A  a i  x  mod ( x n  1), i  1, k  Trong đó k là cấp của a  x  . Một số tính chất của nhóm nhân cyclic: - Tất cả các phần tử của nhóm nhân cyclic là bằng nhau với các trọng số chẵn và trọng sốlẻ - Số lượng các phần tử của nhóm nhân A bằng với cấp của a  x  , có nghĩa là: A  k m - Theo lý thuyết Lagrange thì k là ước số của 2  1 : k | 2m  1 - Tích của hai nhóm nhân cyclic là một nhóm nhân cyclic [8]. m - Hiển nhiên, n là ước số của 2  1 : n | 2m  1 Với m  max deg  f i  x   , fi  x  là các đa thức bất khả quy trong phân tích của x n  1 Định nghĩa 4: Cấp của đa thức ord a  x  là số nguyên dương nhỏ nhất k được xác địnhtheo công thức:  a k  x   e  x  mod x n  1  Trong đó e  x  là một lũy đẳng nào đó. a  x  tạo nên một nhóm nhân cyclic với cấp là k trong nhóm nhân của vành.Tạp chí Nghiên cứu KH&CN quân sự, Số 35, 02 - 2015 45 Kỹ thuật điện tử & Khoa học máy tính Định lý 2:[5] Cấp cực đại của đa thức a  x  trên vành đa thức được xác định theo công thức(với n lẻ): max ord a  x   2m  1 Nếu a  x  là một phần tử của nhóm nhân, cấp cực đại của a  x  được xác định theo: ...