Một số phương pháp mới xác định cấp của đa thức trên vành đa thức sử dụng tính chất của nhóm nhân cyclic đối xứng

Chia sẻ: Wang Ziyi | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

28
lượt xem 2
download

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

Việc tìm được nhóm nhân đạt cấp cực đại trong vành đa thức có ý nghĩa và vai trò quan trọng nhất trong việc cấu trúc lên mã cyclic cục bộ. Bài báo này sẽ đề xuất một số phương pháp mới xác định các cấp của các đa thức trên vành đa thức sử dụng tính chất của nhóm nhân cyclic đối xứng. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Một số phương pháp mới xác định cấp của đa thức trên vành đa thức sử dụng tính chất của nhóm nhân cyclic đối xứng

Hội+ӝL7KҧR4XӕF*LDYӅĈLӋQ7ӱ7UX\ӅQ7K{QJYj&{QJ1JKӋ7K{QJ7LQ(&,7
Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015) Một số phương pháp mới xác định cấp của đa thức trên vành đa thức sử dụng tính chất của nhóm nhân cyclic đối xứng Nguyễn Trung Hiếu Khoa Kỹ thuật Điện tử 1, Học viện Công nghệ Bưu chính Viễn thông, Hà Nội, Việt Nam Email: hieunt@ptit.edu.vn Tóm tắt– Mã cyclic cục bộ (LCC) là một mã khối được tạo giảm độ phức tạp tính toán, rút ngắn thời gian tính toán tới thành dựa trên các phân hoạch của vành đa thức. Phương pháp mức tối đa và đặc biệt là có thể xác định được cấp của toàn bộ điển hình xây dựng mã LCC là dựa trên nhóm nhân cyclic với ưu các đa thức trên các vành lớn mà các nghiên cứu trước đây điểm nổi bật là số lượng mã có thể tạo ra bởi phương pháp này chưa đề cập. nhiều hơn phương pháp tạo mã cyclic dựa trên Ideal. Việc tìm được nhóm nhân đạt cấp cực đại trong vành đa thức có ý nghĩa Nội dung bài báo được chia làm năm phần. Phần II, trình và vai trò quan trọng nhất trong việc cấu trúc lên mã cyclic cục bày sự phân bố đa thức dựa trên cấp của đa thức trên nhóm bộ. Bài báo này sẽ đề xuất một số phương pháp mới xác định các nhân cyclic. Trong phần III, đề xuất một phương pháp chứng cấp của các đa thức trên vành đa thức sử dụng tính chất của minh tính chất của nhóm nhân cyclic đối xứng, trong khi phần nhóm nhân cyclic đối xứng. IV đề xuất hai thuật toán mới xác định cấp của đa thức trên vành và thảo luận về sự cần thiết của chúng. Cuối cùng, kết Từ khóa– Mã cyclic cục bộ (LCC-Local Cyclic Code), Nhóm luận bài báo được trình bày trong phần V. nhân cyclic (CMG- Cyclic Multiplicative Group), Vành đa thức, phân hoạch. II. PHÂN BỐ ĐA THỨC DỰA TRÊN CẤP CỦA ĐA THỨC TRÊN NHÓM NHÂN CYCLIC I. GIỚI THIỆU Lý thuyết mã hóa đã được nghiên cứu và ứng dụng trong Định nghĩa 1: [10] CMG trên 2 > x@ / xn 1 là tập hợp rất nhiều lĩnh vực của cuộc sống, đặc biệt là trong lĩnh vực truyền thông. Lý thuyết về mã hóa phát triển theo ba hướng A ^a x
, i i 1, 2,....` , với a x
2 > x@ / xn 1\ ^0` lớn đó là: mã nguồn, mã kênh (có khả năng phát hiện và sửa lỗi) và mật mã [1], [2]. Mã cyclic là một lớp mã quan trọng ord a x
A
trong các mã khối tuyến tính, có khả năng phát hiện và sửa lỗi tốt, được ứng dụng trong điện tử dân dụng, các hệ thống lưu trữ, các hệ thống truyền thông vì có nhiều phương pháp mã a x
- phần tử sinh của CMG A . hóa và giải mã hiệu quả. Định nghĩa 2: Cấp của đa thức [9]. Mã cyclic được Eugene Prange nghiên cứu đầu tiên năm 1957 [1] . Ngày nay, mã cyclic vẫn nhận được sự quan tâm từ Cấp của đa thức a( x) 2 [ x] / ( xn 1) (ký hiệu ord a( x) ) các nhà nghiên cứu trên toàn thế giới [3]-[8]. Một hướng là số nguyên dương m nhỏ nhất thỏa mãn: nghiên cứu mới về mã cyclic được biết đến là mã cyclic cục bộ (LCC-Local Cyclic Code) được đưa ra bởi tác giả Nguyễn a m1 ( x) a( x) mod ( x n 1) hoặc Bình vào những năm 1980 [10]. LCC thu hút được nhiều nhà nghiên cứu và một số kết quả nghiên cứu về LCC đã được công bố trên các tạp chí chuyên ngành và hội nghị khoa học a m ( x) e( x) mod ( x n 1)
quốc tế [9]-[14]. Các nghiên cứu trước đây chủ yếu tập trung vào cấu trúc Trong đó e( x) là lũy đẳng trong vành, e( x) e2 ( x) . mã [9], [10], [11], [13], [14], thực hiện cứng hóa bộ mã LCCs [12]. Nhìn chung, LCC được xây dựng dựa trên cấu trúc và Như vậy, a( x) tạo nên một nhóm cyclic cấp m vành. phân hoạch CMG của vành đa thức [9], [11]. Định lý 1: [9] Xét a( x) là phần tử của nhóm nhân nào đó, Tuy nhiên, thuật toán xác định cấp của đa thức trên vành cấp cực đại của a( x) được xác định như sau: đa thức đến nay mới chỉ sử dụng phương pháp vét cạn có độ phức tạp lớn, bị hạn chế về năng lực và thời gian tính toán. Bài báo này nghiên cứu một phương pháp chứng minh tính chất - Nếu n lẻ ( n 2k 1 ) và x n 1 f ( x) ; i trong đó của nhóm nhân cyclic đối xứng, đề xuất hai bổ đề phân bổ đa f i ( x) là các đa thức bất khả quy. Khi đó thức trong nhóm nhân cyclic theo cấp và đề xuất các thuật max ord (a( x)) m 2 1 . Trong đó m max deg fi ( x) . toán cải tiến xác định cấp của đa thức trên vành nhằm làm ISBN: 978-604-67-0635-9 248
Hội+ӝL7KҧR4XӕF*LDYӅĈLӋQ7ӱ7UX\ӅQ7K{QJYj&{QJ1JKӋ7K{QJ7LQ(&,7
Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015) - Nếu n chẵn ( n 2s (2k 1) ) và x 2k 1 1 f ( x) ; i Như vậy, ta có: bmk ( x) a( x)mk k e( x) trong đó fi ( x) là các đa thức bất khả quy. Khi đó Bổ đề được chứng minh. max ord (a( x)) 2s (2m 1) . Trong đó m max deg fi ( x) . Bổ đề 2: Số các đa thức đạt cấp cực đại trên vành được Bổ đề 2.1: Trong một nhóm nhân cyclic cấp m , cấp của đa tính bằng N .M (m) , với m là cấp cực đại và N là số nhóm thức thứ k bằng: nhân cyclic đạt cấp cực đại độc lập (nghĩa là không có nhóm nhân nào là hoán vị của nhóm nhân khác). m Chứng minh: mk
gcd m, k
Theo hệ quả của bổ đề 1, số đa thức đạt cấp cực đại trong một nhóm nhân cyclic được tính bởi hàm Phi-Euler ( M (m) ). Hệ quả: Trong một nhóm nhân cyclic cấp m thì: Bổ đề hiển nhiên đúng. + Các đa thức tại vị trí thứ k nguyên tố cùng nhau với m thì có cấp bằng m , nghĩa là GCD m, k
1 thì mk m . Ví dụ 1: Xét vành đa thức 2 [ x] / ( x5 1) , không xét lũy đẳng nuốt en ( x) 1 x x x x 4 , có 2 nhóm nhân như 2 3 + Số đa thức đạt cấp m là M (m) . Trong đó: sau: 1· § M m
m ¨1 e e ek ¸ là hàm Phi-Euler, với m p11 . p22 ... pk ; ° 012
, 024
, 3
, 034
, 023
, 1
, 123