Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng
![Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 1 Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 1](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/366/luan-an-ve-mot-phuong-phap-xay-dung-ham-bam-cho-viec-xac-thu-trang-1_eaTisYkozn.jpg)
Trang 1
![Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 2 Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 2](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/366/luan-an-ve-mot-phuong-phap-xay-dung-ham-bam-cho-viec-xac-thu-trang-2_p7GRdRCQhV.jpg)
Trang 2
![Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 3 Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 3](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/366/luan-an-ve-mot-phuong-phap-xay-dung-ham-bam-cho-viec-xac-thu-trang-3_XPsnw7L3uo.jpg)
Trang 3
![Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 4 Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 4](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/366/luan-an-ve-mot-phuong-phap-xay-dung-ham-bam-cho-viec-xac-thu-trang-4_orIIVVUKJM.jpg)
Trang 4
![Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 5 Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 5](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/366/luan-an-ve-mot-phuong-phap-xay-dung-ham-bam-cho-viec-xac-thu-trang-5_ptiR9Uu39I.jpg)
Trang 5
![Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 6 Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 6](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/366/luan-an-ve-mot-phuong-phap-xay-dung-ham-bam-cho-viec-xac-thu-trang-6_EnUaQJ8D5x.jpg)
Trang 6
![Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 7 Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 7](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/366/luan-an-ve-mot-phuong-phap-xay-dung-ham-bam-cho-viec-xac-thu-trang-7_HvUW1XwAKt.jpg)
Trang 7
![Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 8 Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 8](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/366/luan-an-ve-mot-phuong-phap-xay-dung-ham-bam-cho-viec-xac-thu-trang-8_lXmfMWU09b.jpg)
Trang 8
![Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 9 Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 9](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/366/luan-an-ve-mot-phuong-phap-xay-dung-ham-bam-cho-viec-xac-thu-trang-9_OugsOS6BFM.jpg)
Trang 9
![Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 10 Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng trang 10](https://s1.thuvienluanvan.org/d2fndtiye73ondva/image/2024/03/02/366/luan-an-ve-mot-phuong-phap-xay-dung-ham-bam-cho-viec-xac-thu-trang-10_vUEiEbTfs6.jpg)
Trang 10
Tải về để xem bản đầy đủ
Bạn đang xem 10 trang mẫu của tài liệu "Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
Tóm tắt nội dung tài liệu: Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng
![Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng Luận án Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng](https://s1.thuvienluanvan.org/d2fndtiye73ondva/thumb/2024/03/02/luan-an-ve-mot-phuong-phap-xay-dung-ham-bam-cho-viec-xac-thu_oDxjw5x1H9.jpg)
in rằng văn bản xuất phát từ người sở hữu khóa bí mật. Cả hai bên tham gia vào quá trình thông tin đều có thể tin tường là văn bản không bị sửa đổi trong khi truyền vì nếu văn bản bị thay đổi thì mã băm sẽ thay đổi và lập tức bị phát hiện. 47 Các bước tạo chữ ký và kiểm tra chữ ký được mô tả trên hình sau: Hình 1.17. Quá trình tạo chữ ký số và kiểm tra chữ ký số Ví dụ 1.6: Sơ đồ chữ ký số sử dụng RSA như hình 1.18. Hình 1.18. Sơ đồ chữ ký số dùng RSA 48 Quá trình ký: Băm thông báo M để có mã băm: HHMMDC () Mã hóa mã băm HMDC bằng hệ mật RSA với khóa bí mật của A (dA): dA DSAA H( M ) mod n được chữ ký số của DSA. Ghép chữ ký số DSA với thông báo: M|| DSA và truyền đi. Quá trình kiểm tra: Tách thông báo M và chữ ký số DSA. Giải mã RSA chữ ký số bằng khóa công khai của A (eA) để thu được mã băm của bên phát. Tiến hành băm M để tạo mã băm độc lập: HMDC và so sánh với mã băm bên phát. Nhận xét: Sơ đồ này không bảo mật thông báo M. Để bảo mật thông báo người ta sử dụng sơ đồ chữ ký số dạng như hình 1.19. Hình 1.19. Sơ đồ chữ ký số dùng RSA và có bảo mật thông báo 49 1.6. KẾT LUẬN CHƯƠNG 1 Trong chương 1, luận văn tập trung tìm hiểu các vấn đề chung nhất về mật mã khóa bí mật (hay còn gọi là mật mã cổ điển); mật mã khóa công khai (hay mật mã hiện đại) và hàm băm, từ đó phân tích các ưu và nhược điểm của từng hệ mật. Các nghiên cứu về cấu trúc nhóm nhân và cấp số nhân cyclic trên vành đa thức cho các kết quả khá lý thú trong việc xây dựng các mã sửa sai và mật mã. Để tăng chiều dài cho mật mã khối có thể sử dụng cấu trúc các cấp số nhân cyclic trong các hàm mật mã, nội dung này sẽ được trình bày trong chương 2. 50 CHƯƠNG 2. HỆ MẬT XÂY DỰNG TRÊN CÁC CẤP SỐ NHÂN CYCLIC 2.1. NHÓM NHÂN CYCLIC TRÊN VÀNH ĐA THỨC 2.1.1. Định nghĩa nhóm nhân cyclic trên vành đa thức Định nghĩa 2.1 [6], [10]: Nhóm nhân cyclic (CMG-Cyclic Multiplicate Group) 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. Trong vành đa thức có 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 { , 23 , ..., m } (2.1) Trong đó: A là nhóm nhân cyclic là phần tử sinh (đa thức sinh), . m là cấp của nhóm nhân, cũng chính là cấp của phần tử sinh . Cấp của nhóm là tổng số các phần tử của nhóm. Phần tử đơn vị của nhóm chính là một lũy đẳng ex() có cấp bằng 1. Định nghĩa 2.2 [6], [10]: n Trong vành đa thức Z2[xx ]/ 1, nếu tồn tại một đa thức mà bình phương của nó lại bằng chính nó thì được gọi là đa thức lũy đẳng và ký hiệu là ex(). 22 e()()() x e x e x (2.2) Các lũy đẳng ex() được xác định trên cơ sở phân tích chu trình Cs . n 1 n i Trong mỗi vành đa thức Z2[xx ]/ 1 đều tồn tại một lũy đẳng e0 () x x , i 0 lũy đẳng này được gọi là lũy đẳng “nuốt” (Swallowing Idempotent). 51 Trong một vành bất kỳ, với n lẻ luôn tồn tại một lớp kề chỉ chứa một lũy đẳng “nuốt” ex0 (). * Tính chất của lũy đẳng “nuốt” n - Nếu đa thức a( x ) Z2 [ x ]/ x 1 và trọng số của ax() (ký hiệu là W( a ( x )) ) là số lẻ thì a( x ). e00 ( x ) e ( x ). n - Nếu đa thức b( x ) Z2 [ x ]/ x 1 và W( b ( x ))là số chẵn thì b( x ). e0 ( x ) 0. * Các chu trình Cs Các chu trình Cs theo modulo n trên trường GF(2) được xác định như sau: 2 ms 1 ms 1 Cs s, s .2, s .2 ,..., s .2 trong đó s.2 s mod n Khi đó tập các số nguyên theo modulo n được phân hoạch thành các chu trình. Ta có: {0,1,2,3,...,nC } s s * Ý nghĩa của các chu trình: n Số các chu trình cho ta biết số các đa thức bất khả quy trong vành Z2[xx ]/ 1 Lực lượng của các chu trình cho ta biết bậc của đa thức bất khả quy tương ứng trong phân tích của nhị thức xn 1. Các số trong một chu trình cho biết số mũ tương ứng của đa thức lũy đẳng ex() Định lý 2.1: Cấp của một đa thức ax(), (ký hiệu ord( a ( x )) ), là số nguyên dương m nhỏ nhất thỏa mãn [6], [7], [10]: amn( x ) e ( x )mod( x 1) (2.3) Trong đó ex() là một lũy đẳng nào đó. Như vậy ax() sẽ tạo nên một nhóm cyclic cấp m của vành. Định lý 2.2: Nếu ax() là phần tử của nhóm nhân nào đó thì cấp cực đại của ax() được xác định như sau [6], [7], [8], [10]: 52 n 1 - Nếu n lẻ và x 1 fi ( x ) ; trong đó fxi () là các đa thức bất khả quy. m Khi đó max ord(ax ( )) 2 1, với m maxdeg fi ( x ) . s 21k - Nếu n chẵn nk 2 (2 1) và x 1 fi ( x ) . sm Khi đó max ord(ax ( )) 2 (2 1) , với m maxdeg fi ( x ) . n k Bổ đề 2.1: Trong vành Z2[xx ]/ 1với n 2 ( k nguyên dương), tập các đa thức có trọng số lẻ sẽ tạo nên một nhóm nhân G các đa thức theo modulo xn 1 [7], [8], [9]. Bổ đề 2.2: Mọi phần tử trong nhóm nhân G có cấp là 2k hoặc có cấp là ước của 2k [7], [8], [9] [11], [12]. Bổ đề 2.3: Số các thặng dư bậc hai trong nhóm nhân G của vành được xác định như sau [7], [8], [9]: k 1 Q 221 (2.4) * Các phần tử cấp n và các nhóm nhân cyclic cấp n. i Xét a() x G . a() x ai x . Ta có bổ đề sau: Bổ đề 2.4: Đa thức ax() là phần tử cấp n khi nó có chứa một số lẻ các đơn thức có mũ lẻ có cấp n và một số chẵn các đơn thức có mũ chẵn có cấp là ước của n. Số các đa thức cấp n bằng 2n 2 [1]. Ví dụ 2.1: Với n = 8, có tất cả 26 64 các phần tử cấp n. Ta có thể sử dụng các phần tử này để xây dựng các nhóm nhân cyclic cấp n . 2 3nn 1 0 Ai {(), axaxax i i (), i (), a i (), xaxax i () i ()1} Có tất cả 2n 2 các nhóm nhân cyclic cấp n và nhóm nhân I cũng thuộc vào lớp các nhóm nhân này. Ta gọi I là nhóm nhân cyclic đơn vị. 2.1.2. Các loại nhóm nhân cyclic trên vành đa thức 2.1.2.1. Nhóm nhân cyclic đơn vị Định nghĩa 2.3: Nhóm nhân cyclic đơn vị là một nhóm nhân bao gồm mọi đơn thức có trong vành và nó có cấp là n. Ký hiệu là I { x , x21 ,..., xn ,1} [4], [6]. 53 Hay nói cách khác nhóm nhân cyclic đơn vị là nhóm nhân cyclic có phần tử sinh là x. I { x ,( x )2 ,( x ) 3 ...,( x )n 1 ,1} 2.1.2.2. Nhóm nhân cyclic với phần tử sinh ax() Định nghĩa 2.4: Nhóm nhân cyclic với phần tử sinh là đa thức ax() bao gồm các phần tử là lũy thừa của phần tử sinh và có thể viết dưới dạng sau [6], [10]: A ( a ( x ), a23 ( x ), a ( x ),..., am ( x )} (2.5) Trong đó: m là cấp của ax(). 2.1.2.3. Đa thức đối xứng và các nhóm nhân cyclic đối xứng Định nghĩa 2.5: (Đa thức đối xứng) [6], [10] Đa thức ax()được gọi là đa thức đối xứng với đa thức ax() nếu: i j a() x ai x thì a() x aj x ax() iI jJ Với: I J= ; I J S 0,1,..., n 1 . Bổ đề 2.5: Nếu ax() là một phần tử cấp k thì cấp của ax() cũng bằng k . Tức là, nếu A là một nhóm nhân cyclic cấp có phần tử sinh là ax() thì A cũng là nhóm nhân cyclic cấp với phần tử sinh là ax() [6], [10]. Khi đó ta có: A { a ( x ), a2 ( x ), a 3 ( x ),..., ak 1 ( x )} A { a ( x ),( a ( x ))2 ,( a ( x )) 3 ,...,( a ( x ))k 1 } (2.7) Như vậy, với mỗi phần tử ax() của nhóm nhân cyclic A ta có tương ứng một phần tử ax() của nhóm nhân cyclic A. Từ nhóm nhân cyclic A ta dễ dàng thiết lập được nhóm nhân cyclic A. Hai nhóm nhân A và A được gọi là hai nhóm nhân cyclic đối xứng trong vành đa thức. Từ việc khảo sát các nhóm nhân đối xứng trong vành đa thức ta thấy chỉ cần khảo sát các nhóm nhân trong một nửa vành là ta có thể suy ra kết quả khảo sát 54 cho toàn bộ vành. Khi coi mỗi nhóm nhân là một mã tương ứng mà ta có thể xây dựng được trên nó, ta sẽ khảo sát được các mã trên vành. 2.2. CẤP SỐ NHÂN CYCLIC TRÊN VÀNH ĐA THỨC 2.2.1. Khái niệm về cấp số nhân cyclic trên vành đa thức n Xét vành đa thức Z2[xx ]/ 1 với n lẻ. Định nghĩa 2.6: 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 [6], [10]: 21m A(,)aq {(), axaxqxaxqx ()(), () (),..., axq () ()} x (2.8) Trong đó: m là số các số hạng của cấp số nhân. ax()là số hạng đầu của cấp số nhân. qx() là công bội. a( x ) qmn ( x ) a ( x )mod x 1 Giá trị của m chính là cấp của nhóm nhân sinh với phần tử sinh qx() và lũy đẳng qxm (). Cấp lớn nhất của phần tử qx()được xác định bởi định lý 2.2. Trong trường hợp ta chọn số hạng đầu ax( ) 1, công bội là qx() thì 21m A(1,q ) {1, q ( x ), q ( x ),..., q ( x )} q( x ) q0 ( x ) 1 Là một cấp số nhân cyclic cấp m. n Như vậy, trong vành đa thức Z2[ x ] / x 1, nếu ta chọn số hạng đầu ax()và hạt nhân phân hoạch qx() khác nhau thì ta sẽ tạo ra nhiều kiểu phân hoạch khác nhau của vành, do đó ta có các cấp số nhân cyclic để xây dựng được các mã cyclic có cấu trúc khác nhau. * Các cấp số nhân cyclic cấp n 55 Nếu ta nhân các phần tử của một nhóm nhân cyclic cấp n với một phần tử bất kỳ trong nhóm nhóm nhân G của vành đa thức ta sẽ thu được một cấp số nhân có công bội là phần tử sinh của nhóm nhân và có số hạng ban đầu là đa thức đem nhân. Bổ đề 2.6: Số các cấp số nhân cyclic cấp n xây dựng được trong G trên vành k x2 1 ( nguyên dương) được xác định như sau [7], [8], [9]: k kk N 22 2 .2 2 2 (2.9) Ví dụ 2.2: n Số cấp số nhân N n Số cấp số nhân N n 8 N 28 1 .2 8 2 2 13 8.192 n 64 N 264 1 .2 64 2 2 125 n 16 N 216 1 .2 16 2 2 29 65.011.712 n 32 N 232 1 .2 32 2 2 61 2.2.2. 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 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. 2.2.2.1. Các bước phân hoạch vành đa thức Để phân hoạch một vành đa thức ta thực hiện theo các bước sau đây [6], [7]: n Bước 1: + Chọn một phần tử sinh a( x ) z Z2 [ x ] / x 1. + Xây dựng nhóm nhân cyclic: A { ai ( x ), i 1,2,..., m }, trong đó: m ord a ( x ) . + SA ; n Bước 2: + Chọn b( x ) {¢ 2 [ x ]/ x 1\ S }. + Xây dựng cấp số nhân cyclic: B b( x ). A { b ( x ). ai ( x ), i 1,2,..., m } + SSB 56 n Bước 3: Lặp lại bước 2 cho đến khi S Z2[ x ]/ x 1 Thông số m là cấp của ax() được xác định theo định lý 2.1. Giá trị m chỉ có thể bằng max ord ax ( ) hoặc ước số của . Do vành đa thức có cấu trúc đối xứng, một nửa vành gồm các phần tử có trọng số lẻ, một nửa vành gồm các phần tử có trọng số chẵn. Vì vậy khi phân hoạch ta chỉ cần tìm các phần tử có trọng số lẻ của vành rồi có thể dễ dàng suy ra các phần tử chẵn. Để xây dựng được tất cả các nhóm nhân của vành ta thực hiện các bước sau: Xác định tất cả các đa thức lũy đẳng trong vành, trên cơ sở phân tích các chu trình. Chọn các đa thức lũy đẳng có trọng số lẻ để xây dựng các nhóm nhân chứa chúng. Xây dựng tất cả các nhóm nhân cyclic có thể có của vành. Tùy theo từng lũy đẳng mà mỗi lũy đẳng có thể tham gia trong nhiều nhóm nhân. Lấy đối xứng tất cả các nhóm nhân có chứa các phần tử có trọng số lẻ sẽ tạo được tất cả các nhóm nhân có chứa các phần tử có trọng số chẵn. 2.2.2.2. Phân hoạch vành đa thức suy biến và không suy biến Có nhiều dạng phân hoạch vành đa thức khác nhau, song dạng phân hoạch chung nhất là phân hoạch suy biến và phân hoạch không suy biến. Định nghĩa 2.7: Phân hoạch vành đa thức được gọi là không suy biến nếu phân hoạch bao gồm tất cả các phần tử khác 0 trong vành đa thức. Ngược lại, phân hoạch là phân hoạch suy biến [6]. Bổ đề 2.7: Trong một phân hoạch không suy biến tùy ý, số lớp kề trong phân hoạch xác định theo biểu thức sau [6]: 22n N(a ( x ), n ) 1 (2.10) ord( a ( x )) * Điều kiện để phân hoạch không suy biến 57 Định lý 2.3: Điều kiện cần và đủ để phân hoạch vành không suy biến là nhóm nhân sinh của phân hoạch có lũy đẳng bằng 1 [6]. Bổ đề 2.8: Số kiểu phân hoạch không suy biến khác nhau bằng số các bậc khác nhau của các phần tử trong vành (trừ các phần tử lũy đẳng có bậc là 1), ký hiệu là M [6]. Số kiểu phân hoạch không suy biến khác nhau chính là số ước khác nhau của giá trị cấp lớn nhất của phần tử a(x) (max ord a(x)). Giá trị max ord a(x) . Kết quả tính số kiểu phân hoạch không suy biến M của một số vành được thống kê trong bảng 2.1. Bảng 2.1. Số kiểu phân hoạch không suy biến M của một số vành n max ord ax() Phân tích của max ord ax() M 5 15 3.5 3 7 7 7 1 9 63 3.3.7 5 11 1023 3.11.31 7 13 4095 3.3.5.7.13 16 15 15 3.5 3 Bổ đề 2.9: Số kiểu phân hoạch suy biến (ký hiệu là I) bằng số Ideal trong vành đa thức [6]. n Trong vành đa thức Z2[xx ]/ 1, số Ideal của vành được xây dựng tương ứng với các đa thức sinh gx(), mỗi Ideal tương ứng với bộ mã cyclic (theo quan điểm xây dựng mã cyclic cổ điển). Các đa thức sinh gx()tương ứng với mỗi Ideal được lập từ tổ hợp các đa thức bất khả quy trong phân tích của nhị thức xn + 1. t n x 1 fit ( x ) f12 ( x ). f ( x )... f ( x ) , với degfi ( x ) n i i 1 58 s n g() x fjs () x f12 ().()...() x f x f x , với gx() | x + 1, degfj ( x ) n j j 1 Như vậy, số đa thức sinhI g({x x) ,( (tương x )2 ,( x )ứ 3ng ...,( là x )Ideal)n 1 ,1} có thể thiết lập được từ t đa t 1 n i thức bất khả quy trong phân tích nhị thức x + 1 được xác định: I Cm . i 1 Bổ đề 2.10: Tổng số các kiểu phân hoạch có trong một vành đa thức (ký hiệu là C) được xác định bởi biểu thức: C=M.I [6]. n n Tổng số các kiểu phân hoạch C của một số vànhZ2[xx ]/Z2[xx ]/ 1 1 khác nhau như trong trong bảng 2.2. Bảng 2.2. Tổng số các kiểu phân hoạch của vành Số đa thức bất khả quy n M I C = M.I trong phân tích xn + 1 5 2 3 2 6 7 3 1 6 6 9 3 5 6 30 11 2 7 2 14 13 2 16 2 32 15 5 3 30 90 n Như vậy, trong một vành đa thức Z2[xx ]/ 1, với mỗi giá trị n thì số kiểu phân hoạch cũng khá nhiều, tạo ra khả năng lớn để chọn dạng mã cyclic có đặc tính sửa sai tốt. Trong mỗi dạng mã đã xác định, ta tiến hành lựa chọn các mã sửa sai tối ưu để sử dụng. 2.2.2.3. Các loại phân hoạch a) Phân hoạch chuẩn Phân hoạch chuẩn hay phân hoạch theo I – nhóm nhân cyclic đơn vị [6]. (2.11) Hạt nhân của phân hoạch là x, có cấp ord(xn ) . 59 + Các lớp kề có độ lớn bằng n hoặc ước của n. Bổ đề 2.11: Trong phân hoạch chuẩn thì số lớp kề trong phân hoạch được xác định theo biểu thức [6]: 22n N(,)xn 1 (2.12) n + Khi n là số nguyên tố thì có thể tính chính xác được số lớp kề. n 1 i Có một lớp kề chỉ chứa e0 x x , số phần tử còn lại trong các lớp kề là i 1 22n 22n . Do đó số các lớp kề là: N 1. n b) Phân hoạch cực đại Định nghĩa 2.8: Phân hoạch được gọi là cực đại nếu nhóm nhân cyclic sinh có phần tử sinh n với cấp lớn nhất, ord a ( x ) maxord b ( x ); b ( x ) Z2 [ x ]/ x 1 [6]. Bổ đề 2.12: Trong phân hoạch cực đại thì số lớp kề của phân hoạch được xác định theo công thức sau [6]: 22n N(a ( x ), n ) 1 (2.13) maxord ( b ( x )) c) Phân hoạch cực tiểu Định nghĩa 2.9: 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 cyclic là ax( ) 1 [6]. Bổ đề 2.13: Trong phân hoạch cực tiểu với phần tử của nhóm nhân ax( ) 1, số lớp kề trong phân hoạch được xác định [6]: n N(1,n ) 21 (2.14) Trong phân hoạch cực tiểu, mỗi lớp kề chỉ gồm 1 phần tử, do vậy số lớp kề trong phân hoạch này đúng bằng số phần tử khác 0 có trong vành: 2n – 1 . 60 d) Phân hoạch vành thành các cấp số nhân có cùng trọng số i i Trong trường hợp q() x x và ord(xn ) thì cấp số nhân A(,)aq 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ố. Dạng phân hoạch này chính là phân hoạch không suy biến và phân hoạch theo nhóm nhân đơn vị. e) Phân hoạch vành thành các phần tử có trọng số cùng tính chẵn lẻ. Xét cấp số nhân cyclic có dạng sau [6]: 21m A(,)aq {(), axaxqxaxqx ()(), () (),..., axq () ()} x (2.15) - Nếu W( q ( x )) lẻ. + Phần tử đầu tiên ax() là đa thức có trọng số lẻ thì tất cả các phần tử của cấp số nhân đều là đa thức có trọng số lẻ. Vì tích của các đa thức có trọng số lẻ là một đa thức có trọng số lẻ. + Phần tử đầu tiên ax() là đa thức có trọng số chẵn thì tất cả các phần tử của cấp số nhân đều là đa thức có trọng số chẵn. Vậy khi lẻ các lớp kề có các đa thức có trọng số chẵn hoặc lẻ. - Nếu chẵn, với phần tử đầu tiên ax() là đa thức bất kỳ thì tất cả các phần tử của cấp số nhân đều là đa thức có trọng số chẵn phân hoạch suy biến. Tóm lại, nếu công bội qx() (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ố. f) Phân hoạch vành đa thức thành các cấp số nhân theo modulo h(x). n Vành đa thức Z2[xx ]/ 1 có thể được phân hoạch thành các cấp số nhân theo modulo hx() với h( x ) | xn 1 [6], [7], [8]. n Từ phân tích nhị thức x 1 f12 ( x ). f ( x )... ft ( x ) 61 Trong đó, fi(x) là các đa thức bất khả quy. Như vậy, hx() là tổ hợp của các fi(x) sao cho deg degh ( x ) k n. Tuỳ theo giá trị n mà có số đa thức bất khả quy khác nhau, nên sẽ có số hx()khác nhau. Khi đó, trên vành sẽ có nhiều phân hoạch ứng với các hx()khác nhau. Trong trường hợp này phân hoạch vành chỉ gồm 2k – 1 phần tử cho nên phân hoạch sẽ suy biến và vành đa thức bị suy biến thành các vành nhỏ hơn. 2.3. XÂY DỰNG M-DÃY LỒNG GHÉP TRÊN VÀNH ĐA THỨC CÓ HAI LỚP KỀ CYCLIC 2.3.1. Vành đa thức có hai lớp kề Định nghĩa 2.10 Vành đa thức theo modulo xn 1 được gọi là vành đa thức có hai lớp kề cyclic nếu phân tích của 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 [2]: n 1 xni 1 (1 x ) x (2.16) i 0 n 1 i Trong đó và e0 () x x là các đa thức bất khả quy. i 0 Bổ đề 2.14 Vành đa thức theo modulo là một vành đa thức có hai lớp kề cyclic nếu n thoả mãn [2], [7], [8]: n phải là một số nguyên tố; phần tử thứ hai phải thoả điều kiện 2 (np )/ 1modn với mỗi ước nguyên tố p của (n). (Trong đó (n) là hàm phi Euler) Thuật toán xác định giá trị n [8], [9], [10], [11] Vào: số nguyên tố n Bước 1: tìm phân tích của (n-1); xác định các ước nguyên tố pi của phân tích này. 62 n 1/ pi Bước 2: với mỗi pi tính 2 np 1/ i - Nếu tồn tại pi sao cho 2 1(modn ) thì n không thoả mãn. - n thoả mãn trong các trường hợp còn lại. Ra: Giá trị n thoả mãn. Theo thuật toán này ta xác định được một số giá trị n đảm bảo vành đa thức theo mod xn+1 là một vành đa thức có hai lớp kề cyclic. Dưới đây là một số giá trị n thỏa mãn. n = 3 5 11 13 19 29 37 53 59 61 67 83 101 107 131 139 149 163 173 179 181 197 211 227 269 293 317 347 349 373 379 389 419 421 443 461 467 491 509 523 541 547 557 563 587 613 619 653 659 661 677 701 709 757 773 787 797 821 827 829 853 859 877 883 907 941 947 1019 1061 1091 1109 1117 1123 1171 1187 1213 1229 1237 1259 1277 1283 1291 1301 1307 1373 1381 1427 1451 1453 1483 1493 1499 1523 1531 1549 1571 1619 1621 1637 1667 1669 1693 1733 1741 1747 1787 1861 1867 1877 1901 1907 1931 1949 1973 1979 1987 1997 2027 2029 2053 2069 2083 2099 2131 2141 2213 2221 2237 2243 2267 2269 2293 2309 2333 2339 2357 2371 2389 2437 2459 2467 2477 2531 2539 2549 2557 2579 2621 2659 2677 2683 2693 2699 2707 2741 2789 2797 2803 2819 2837 2843 2851 2861 2909 2939 2957 2963 3011 3019 3037 3067 3083 3187 3203 3253 3299 3307 3323 3347 3371 3413 3461 3467 3469 3491 3499 3517 3533 3539 3547 3557 3571 3581 3613 3637 3643 3659 3677 3691 3701 3709 3733 3779 3797 3803 3851 3853 3877 3907 3917 3923 3931 3947 3989 4003 4013 4019 4021 4091 4093 4099 4133 4139 4157 4219 4229 4243 4253 4259 4261 4283 4349 4357 4363 4373 4397 4451 4483 4493 4507 4517 4547 4603 4621 4637 4691 4723 4787 4789 4813 4877 4933 4957 4973 4987 5003 5011 5051 5059 5077 5099 5107 5147 5171 5179 5189 5227 5261 5309 5333 5387 5443 5477 5483 5501 5507 5557 5563 5573 5651 5659 5683 5693 5701 5717 5741 5749 5779 5813 5827 5843 5851 5869 5923 5939 5987 6011 6029 6053 6067 6101 6131 6173 6197 6203
File đính kèm:
luan_an_ve_mot_phuong_phap_xay_dung_ham_bam_cho_viec_xac_thu.pdf
HQB Thong tin luan an dua len mang.pdf
tom tat new 12.2013.pdf