Đăng ký Đăng nhập
Trang chủ Các thuật toán tạo m dãy lồng ghép trên vành đa thức có hai lớp kề cyclic...

Tài liệu Các thuật toán tạo m dãy lồng ghép trên vành đa thức có hai lớp kề cyclic

.PDF
13
133
78

Mô tả:

Hiện nay trong nhiều ứng dụng như hệ thống thông tin như WCDMA, đồng bộ đo lường từ xa…các dãy m được sử dụng rất nhiều vì chúng có các tính chất thỏa mãn các tiêu chuẩn của dãy giả ngẫu nhiên. Các m dãy về bản chất là các mã cyclic có chiều dài cực đại với tham số (2n - 1, n, 2n-1) và thường được xây dựng trên các vành đa thức lẻ. Tuy nhiên, đối với vành đa thức có hai lớp kề cyclic thì việc xây dựng mã rất hạn chế. Số mã xây dựng trên vành không nhiều và chỉ có thể xây dựng được các mã tầm thường. Do đó trong luận văn này, tác giả tập trung vào nghiên cứu việc xây dựng các m dãy trên vành đa thức có hai lớp kề cyclic. Luận văn này được chia thành 4 chương và phần phụ lục. Chương 1: Cơ sở đại số Chương này trình bày những vấn đề chung về lý thuyết số, cấu trúc đại số để xây dựng mã cyclic, m dãy trên vành đa thức. Chương 2: Vành đa thức có hai lớp kề cyclic Chương này trình bày các khái niệm vành đa thức có 2 lớp kề cyclic. Các vấn đề cơ bản của phân hoạch vành đa thức. Chương 3: Một số phương pháp tạo m dãy Chương này giới thiệu một số phương pháp tạo m dãy đã được sử dụng rộng rãi trong thực tế. Chương 4: Xây dựng m dãy trên vành đa thức có hai lớp kề cyclic Chương này trình bày một số phương pháp tạo m dãy trên vành đa thức có hai lớp kề cyclic. Lý thuyết xây dựng mã và các bộ mã hóa, giải mã cho một số m dãy cụ thể. Phần phụ lục: Phụ lục: Phương pháp giải mã ngưỡng
BỘ GIÁO DỤC VÀ ĐÀO TẠO TẬP ĐOÀN BƯU CHÍNH VIỄN THÔNG VIỆT NAM HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- NGUYỄN THỊ HƯƠNG THẢO CÁC THUẬT TOÁN TẠO M DÃY LỒNG GHÉP TRÊN VÀNH ĐA THỨC CÓ HAI LỚP KỀ CYCLIC CHUYÊN NGÀNH : KỸ THUẬT ĐIỆN TỬ MÃ SỐ:260.51.70 TÓM TẮT LUẬN VĂN THẠC SĨ Người hướng dẫn khoa học : GS.TS NGUYỄN BÌNH 1 HÀ NỘI – 2010 MỞ ĐẦU Hiện nay trong nhiều ứng dụng như hệ thống thông tin như WCDMA, đồng bộ đo lường từ xa…các dãy m được sử dụng rất nhiều vì chúng có các tính chất thỏa mãn các tiêu chuẩn của dãy giả ngẫu nhiên. Các m dãy về bản chất là các mã cyclic có chiều dài cực đại với tham số (2 n - 1, n, 2 n-1) và thường được xây dựng trên các vành đa thức lẻ. Tuy nhiên, đối với vành đa thức có hai lớp kề cyclic thì việc xây dựng mã rất hạn chế. Số mã xây dựng trên vành không nhiều và chỉ có thể xây dựng được các mã tầm thường. Do đó trong luận văn này, tác giả tập trung vào nghiên cứu việc xây dựng các m dãy trên vành đa thức có hai lớp kề cyclic. Luận văn này được chia thành 4 chương và phần phụ lục. Chương 1: Cơ sở đại số Chương này trình bày những vấn đề chung về lý thuyết số, cấu trúc đại số để xây dựng mã cyclic, m dãy trên vành đa thức. Chương 2: Vành đa thức có hai lớp kề cyclic Chương này trình bày các khái niệm vành đa thức có 2 lớp kề cyclic. Các vấn đề cơ bản của phân hoạch vành đa thức. Chương 3: Một số phương pháp tạo m dãy Chương này giới thiệu một số phương pháp tạo m dãy đã được sử dụng rộng rãi trong thực tế. Chương 4: Xây dựng m dãy trên vành đa thức có hai lớp kề cyclic Chương này trình bày một số phương pháp tạo m dãy trên vành đa thức có hai lớp kề cyclic. Lý thuyết xây dựng mã và các bộ mã hóa, giải mã cho một số m dãy cụ thể. Phần phụ lục: Phụ lục: Phương pháp giải mã ngưỡng 2 CHƯƠNG 1. CƠ SỞ ĐẠI SỐ Chương này trình bày những vấn đề cơ bản về lý thuyết số, cấu trúc đại số để xây dựng mã cyclic trên vành đa thức. Khái niệm về m dãy và một số tính chất quan trọng của m dãy. 1.1. Cơ sở đại số để xây dựng mã cyclic trên vành đa thức 1.1.1. Những vấn đề cơ bản về lý thuyết số 1.1.2. Những vấn đề cơ bản về cấu trúc đại số 1.2 Vành đa thức và mã cyclic 1.2.1 Vành đa thức 1.2.2 Ideal của vành đa thức 1.2.3 Định nghĩa mã cyclic 1.2.4 Mã cyclic có chiều dài cực đại (m dãy hay dãy m) - Định nghĩa m dãy - Thuộc tính của m dãy: thuộc tính cân bằng, thuộc tính chạy và thuộc tính tương quan. - Sơ đồ tạo m dãy. CHƯƠNG 2 - VÀNH ĐA THỨC CÓ HAI LỚP KỀ CYCLIC Chương này sẽ giới thiệu khái niệm về vành đa thức có hai lớp kề cyclic, điều kiện để vành đa thức có hai lớp kề cyclic. Bên cạnh đó cũng thực hiện khảo sát các phân hoạch trên vành đa thức nói chung và vành đa thức có hai lớp kề cyclic nói riêng. Đáng chú ý trong chương này là phân hoạch vành mở rộng của vành đa thức Z2[x]/xn + 1 theo lớp các phần tử liên hợp. Đây là tiền đề để xây dựng các mã cyclic và m dãy ở chương 4. 2.1 Định nghĩa vành đa thức có hai lớp kề cyclic Vành đa thức theo modulo x n  1 được gọi là vành đa thức có hai lớp kề cyclic nếu phân tích của xn  1 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: n1 xn  1  ( x  1) xi i 0 n 1 Trong đó (x + 1) và e0 ( x )   x i là các đa thức bất khả quy. i 0 3 2.2 Phân hoạch vành đa thức có hai lớp kề cyclic 2.2.1 Nhóm nhân cyclic trên vành đa thức - Nhóm nhân cyclic 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. A = {, 2, 3,…} - Lũy đẳng “nuốt”: Trong mỗi vành đa thức Z2[x]/ xn + 1 đều tồn tại một lũy đẳng n 1 e0(x) =  x i , lũy đẳng này được gọi là lũy đẳng “nuốt” (Swallowing Idempotent). i 0 2.2.3 Phân hoạch suy biến và không suy biến 2.2.4. Các kiểu phân hoạch của vành đa thức - Phân hoạch chuẩn Phân hoạch chuẩn hay phân hoạch theo I – nhóm nhân xyclic đơn vị. Hạt nhân của phân hoạch là x, có cấp ord(x) = n. - Phân hoạch cực đại Phân hoạch được gọi là cực đại nếu nhóm nhân cyclic sinh có phần tử sinh với cấp lớn nhất, ord(a(x)) = max ord(b(x)), b(x)  Zn. - Phân hoạch cực tiểu 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 xyclic là a(x) = 1. - Phân hoạch vành thành các cấp số nhân có cùng trọng số Trong trường hợp q(x) = xi và ord xi = n thì cấp số nhân A(a,q) 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ố. - Phân hoạch vành đa thức thành các cấp số nhân với các phần tử có cùng tính chẵn lẻ của trọng số. Nếu công bội q(x) (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ố. - Phân hoạch vành đa thức thành các cấp số nhân theo modulo h(x). Vành đa thức Z2[x]/ xn + 1 có thể được phân hoạch thành các cấp số nhân theo modulo h(x) với h(x) | xn + 1. Từ phân tích nhị thức xn+ 1 = m  fi ( x)  f1 ( x). f 2 ( x )... f t ( x ) i 1 4 Trong đó, fi(x) là các đa thức bất khả quy. Như vậy, h(x) là tổ hợp của các fi(x) sao cho deg h(x) = k < n, trong vành đa thức Z2[x]/ xn +1. Tuỳ theo giá trị n mà có số đa thức bất khả quy khác nhau, nên sẽ có số h(x) khác nhau. Khi đó, trên vành sẽ có nhiều phân hoạch ứng với các h(x) khác nhau. - Phân hoạch vành mở rộng của vành đa thức có hai lớp kề cyclic theo lớp các phần tử liên hợp + Đa thức f(x) được gọi là thặng dư bậc 2 (quadratic residue - QR) trong Z 2n nếu tồn tại đa thức g(x) sau: 2 2n g ( x )  f ( x ) mod( x  1) Như vậy g ( x)  Z 2 n và được gọi là căn bậc 2 của f(x). Khi g ( x )  f ( x) được gọi là căn bậc 2 chính của f(x). + Các căn bậc 2 của một thặng dư bậc 2 được xác định theo công thức sau:   sqr[ f ( x )]=g(x)=(1+x n )   x t    tU  f ( x) Trong đó U là một tập gồm các tổ hợp tùy ý các giá trị trong tập 0, 1, 2,..., n  1 . Do vậy lực lượng của U sẽ bằng U  2 n  1 . Như vậy đối với mỗi thặng dư bậc 2 trong vành Z 2n có tất cả 2 n căn bậc 2 (kể cả căn bậc 2 chính). Nhận xét:  Trong vành Z 2n có 2 n thặng dư bậc 2, mỗi thặng dư bậc 2 có 2n căn bậc 2, do vậy có tất cả 2 2n căn bậc 2 trong vành.  Mặt khác, ta thấy rằng, trong vành Z 2n có 22 n đa thức (lực lượng các phần tử trong vành được tính bằng Z 2 n  2 2 n ) do vậy các căn bậc 2 của các thặng dư bậc 2 tạo nên toàn bộ vành Z 2 n .  Trong trường số đầy đủ, căn bậc 2 của (-1) là  j , chúng được gọi là các phần tử liên hợp. Tương tự như vậy, ta sẽ gọi các căn bậc 2 của cùng một thặng dư bậc 2 là các phần tử liên hợp (Conjugate Elements) tương ứng với thặng dư đó ký kiệu là CEs. + Tính chất của các phần tử liên hợp: 5  Nếu a(x) là các căn bậc 2 thì các phần tử đối xứng của nó cũng là các căn bậc 2.  Tổng của 2 CEs cũng chính là một căn bậc 2 của zero.  Tổng quát hơn, tổng số chẵn các CEs cũng chính là một căn bậc 2 của zero.  Tổng của 3 CEs cũng chính là một CE. + Phân hoạch vành đa thức theo lớp các phần tử liên hợp. Trong vành đa thức Z2n, các thặng dư bậc 2 khác nhau sẽ có các căn bậc 2 khác nhau. Số các căn bậc 2 toàn bộ các thặng dư bậc 2 sẽ được tính như sau: Q2n .2 n  2 n.2 n  2 2 n Do vậy, tập của các căn bậc 2 của các thặng dư bậc 2 này sẽ là toàn bộ vành đa thức Z2n. Vành nãy sẽ được chia thành lớp bao gồm các phần tử liên hợp. Tập của các phần tử liên hợp này sẽ được gọi là vành của các phần tử liên hợp. 2.3 Kết luận Chương này đã trình bày khái niệm vành đa thức có 2 lớp kề cyclic và các kiểu phân hoạch vành đa thức, đặc biệt là phân hoạch vành đa thức mở rộng Z 2  x  / x 2 n  1 của vành đa thức có 2 lớp kề cyclic Z 2  x  / x n  1 theo lớp các phần tử liên hợp. Đây là cơ sở lý thuyết rất quan trọng để xây dựng m dãy ở chương 4 CHƯƠNG 3 - CÁC PHƯƠNG PHÁP TẠO DÃY M Dãy m đã được nghiên cứu rất nhiều và hiện nay có rất nhiều phương pháp tạo m dãy. Chương này trình bày một số phương pháp cơ bản để tạo chuỗi PN bao gồm: Phương pháp Blum Blum Shub, Phương pháp congruential đảo (Inversive congruential), Phương pháp Cipher (ISAAC), Phương pháp Fibonaci trễ (Lagged Fibonaci), Phương pháp congruential tuyến tính (Linear congruential), Phương pháp thanh ghi dịch có hồi tiếp tuyến tính (Linear feedback shift register), Phương pháp nhân có nhớ (Multiply with carry), Phương pháp xoay Mersenne (Mersenne twister), Phương pháp số nguyên tố Sophie Germain. 6 Ngoài ra, các thuật toán Cipher và các hàm băm mật mã cũng có thể được sử dụng để tạo ra các chuỗi PN. Tuy nhiên, trong chương này tập trung vào các phương pháp tạo chuỗi PN cơ bản. CHƯƠNG 4 - XÂY DỰNG DÃY M TRÊN VÀNH ĐA THỨC CÓ HAI LỚP KỀ CYCLIC 4.1 Xây dựng dãy m lồng ghép trên vành đa thức có hai lớp kề cyclic Dãy m lồng ghép trên vành đa thức có hai lớp kề cyclic có thể được tạo ra từ phương trình đồng dư sau: b( x)  c( x) a i ( x) mod h ( x) i  1,2,...,2 m  1 Trong đó bậc của a(x), orda( x)  2 m  1  2 n1  1 Số lượng a(x) là N a   (2 m  1) với  là hàm Phi-Euler. W (a( x))  wa là một số chẵn W ( h( x))  wh là một số lẻ với deg h ( x)  n  1 ( n 1) / 2 Số lượng hàm h(x) là: N h   C n2i 1  2 n 2 i 0 c(x) là đa thức sinh với deg c( x)  m  1 Số lượng dãy M lồng ghép là N  N a N h Ví dụ: Dãy m lồng ghép trên Z 2[ x]/ x5  1, N h  2n 2  8 , các đa thức h(x) này là: (4), (014), (024), (034), (124), (234), (134), (01234). Giả sử a( x)  x  x 2  (12) (orda( x)  15) h(x) = (01234) Ta có: A7  {(12)i mod(01234); i  1, 2,....} A7  {(12), (013), (2), (012), (023), (0123), (01), (13), (1), (23), (03), (3), (123), (02), (0)}  Sơ đồ mã hóa: (0) (1) (2) (3) (4) 7  Sơ đồ giải mã theo phương pháp giải mã ngưỡng Hệ tổng kiểm tra trực giao: S1  (013)  (13) S 2  (2)  (02) S3  (012)  (12) S 4  (03)  (3) S5  (023)  (23) S6  (0123)  (123) S7  (01)  (1) a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 4.2 Xây dựng dãy m trên vành mở rộng của vành đa thức có hai lớp kề cyclic theo các phần tử liên hợp Tập tất cả các phần tử liên hợp với lũy đẳng nuốt e0(x2) sẽ tạo ra các mã cyclic cục bộ với các giá trị sau: ( n, k , d 0 )  (2n  1, n, 2n 1 ) 4.2.1 Xây dựng dãy m trên các phần tử liên hợp của lũy đẳng nuốt theo phân hoạch chuẩn Thực hiện phân hoạch chuẩn nhưng không phải đối với toàn bộ các phần tử trong vành Z2n mà chỉ phân hoạch chuẩn các phần tử liên hợp của lũy đẳng nuốt e0 ( x 2 ) . Có nghĩa là, chúng ta sẽ xây dựng các cấp số nhân với số hạng đầu a(x) là một phần tử liên hợp bất kỳ của lũy đẳng nuốt e0 ( x 2 ) trong vành đa thức Z2n, nhóm nhân cyclic đơn vị với phần tử sinh q(x) = x. Ví dụ với n = 5. Ta có bảng phân hoạch chuẩn của lũy đẳng nuốt e0 ( x 2 )  (02468) theo các phần tử liên hợp: No C1 C2 C3 C4 8 1 (01234) (02346) (03467) (02468) 2 (12345) (13457) (14578) (13579) 3 (23456) (24568) (25689) 4 (34567) (35679) (36790) 5 (45678) (46780) (47801) 6 (56789) (57891) (58912) 7 (67890) (68902) (69023) 8 (78901) (79013) (70134) 9 (89012) (80124) (81245) 10 (90123) (91235) (92356)  Sơ đồ mã hóa cho mã (31,5,16) theo phân hoạch chuẩn x0 x1 x2 x3 x4 0 0 0 0 0 C1 C2 C3 C4  Sơ đồ giải mã 9 C41 C 2 4 C31 C32 C33 C34 C35 C36 C37 C38 C39 C310 C21 C22 C23 C24 C25 C26 C27 C28 C29 C210 C11 C12 C13 C14 C15 C16 C17 C18 C19 C110 4.2.2 Xây dựng dãy m trên các phần tử liên hợp của lũy đẳng nuốt theo phân hoạch cực đại Phân hoạch cực đại của mã cyclic cục bộ với n lẻ là mã cyclic cục bộ được xây dựng trên nhóm nhân cyclic với công bội a(x). Ở đây ta có: ord a(x)=max ord f(x), f(x)  Z2 [x]/x n  1 Tương tự như vậy, trong vành đa thức Z 2 [x]/x 2n  1 , ta cũng sẽ tiến hành xây dựng mã cyclic cục bộ trên phân hoạch cực đại của vành theo các phần tử liên hợp của lũy đẳng nuốt. Trên vành đa thức Z 2[x]/x 2n  1 , cấp của nhóm nhân sinh cyclic a(x) sẽ bẳng 2.ord a(x) trong Z 2 [x]/x n  1 . Ta sẽ xem xét một nhóm nhân trên vành Z2n qua ví dụ n = 5. Xét vành Z10 với phần tử sinh a(x)=1+x+x2  (012) Ta có phân hoạch cực đại gồm 2 lớp kề: 10 B1  {e0 ( x) a i ( x), i  0, 29}={b1i , i = 1,30} = {(01234), (02346), (01478), (34567), (35679), (01347), (06789), (02689), (03467), (01239), (12359), (03679), (23456), (24568), (02369), (56789), (15789), (23569), (01289), (01248), (25689), (12345), (13457), (12589), (45678), (04678), (12458), (01789), (01374), (14578)} B2 = {(02468), (13579)} = { b21 , b22 }  Sơ đồ mã hóa (0) (1) (2) (3) (4) (0) (0) (0) (0) (0)  Sơ đồ giải mã 11 b22 b21 b130 b129 b128 b127 b126 b125 b124 b123 b122 b121 b120 b119 b118 b117 b116 b115 b114 b113 b112 b111 b110 b19 b18 b17 b16 b15 b14 b13 b12 b11 4.3 Kết luận Trong chương này đã trình bày một số phương pháp tạo và giải mã cho các m dãy trên vành đa thức có hai lớp kề cyclic. Ngoài phương pháp tạo m dãy trên cách vành lẻ, ở đây trình bày phương pháp tạo m dãy trên vành chẵn Z2n, vành mở rộng của vành đa thức có hai lớp kề cyclic. Việc xây dựng m dãy trên vành chẵn dựa vào phân hoạch của vành chẵn theo các phần tử liên hợp của lũy đẳng nuốt. Điều này làm đa dạng hóa các phương pháp tạo m dãy trong lý thuyết mã, cung cấp nhiều lựa chọn hơn cho các m dãy. 12 KẾT LUẬN Vành đa thức có hai lớp kề cyclic là vành đa thức có tính chất đặc biệt, trong đó phân tích nhị thức của vành đa thức chỉ bao gồm hai đa thức. Do đó trên vành này chỉ xây dựng được các mã tầm thường là các mã chẵn, lẻ. Việc tìm hiểu về vành đa thức này chưa được quan tâm nhiều và ít có các ứng dụng trên vành đa thức có hai lớp kề cyclic. Luận văn tập trung vào việc tìm hiểu vành đa thức có hai lớp kề cylic, các cấu trúc nhóm nhân và các kiểu phân hoạch trên vành đa thức có hai lớp kề cyclic nhằm tận dụng tối đa các đặc điểm cũng như khắc phục các hạn chế của vành này. Trong chương 4 đã trình bày một số phương pháp xây dựng m dãy trên vành đa thức có hai lớp kề cyclic. Đó là việc xây dựng m dãy dựa trên nhịp là đa thức a(x) và modulo h(x) không nhất thiết phải là đa thức nguyên thủy. Ngoài ra m dãy còn có thể được xây dựng trên vành chẵn là vành mở rộng Z 2  x  / x 2 n  1 của vành đa thức Z 2  x  / x n  1 theo lớp các phần tử liên hợp của lũy đẳng nuốt. Chương này cũng giới thiệu một số bộ mã hóa và giải mã tương ứng khi xây dựng m dãy theo các phương pháp này. Hướng nghiên cứu tiếp theo của luận văn là đánh giá những đặc tính của m dãy này và các biện pháp để áp dụng một cách khả thi trong các ứng dụng thực tế. Do thời gian nghiên cứu còn hạn chế nên luận văn có thể còn nhiều thiếu sót, rất mong các thầy cô giáo, các đồng nghiệp và bạn bè đóng góp ý kiến bổ sung để luận văn được tốt hơn. 13
- Xem thêm -

Tài liệu liên quan