tailieunhanh - Tìm hiểu hệ mật ELGAMAL và các LOGARITHM rời rạc phần 5

Xây dựng một trường 8 phần tử. Điều này có thể thực hiện bằng cách tìm một đa thức bất khả quy bậc 3 trong Z2[x]. Ta chỉ cần xem xét các đa thức có thành phần hằng số bằng 1 vì một đa thức bất kì có thành phần hằng số bằng 0 sẽ chia hết cho x và bởi vậy nó là một đa thức bất khả quy . | Vietebooks Nguyễn Hoàng Cương Xây dựng một trường 8 phần tử. Điều này có thể thực hiện bằng cách tìm một đa thức bất khả quy bậc 3 trong Z2 x . Ta chỉ cần xem xét các đa thức có thành phần hằng số bằng 1 vì một đa thức bất kì có thành phần hằng số bằng 0 sẽ chia hết cho x và bởi vậy nó là một đa thức bất khả quy . Có tất cả 4 đa thức như vậy. f1 x x3 1 f2 x x3 x 1 f3 x x3 x2 1 f4 x x3 x2 x 1 Xét thấy f1 x là khả quy vì x3 1 x 1 x2 x 1 cần để ý là tất cả các hệ số được rút gọn theo modulo 2 . Tương tự f4 x cũng khả quy vì x3 x2 x 1 x 1 x2 1 Tuy nhiên cả hai đa thức f2 x va f3 x lại đều là đa thức bất khả quy và có thể dùng hai đa thức này để xây dựng trường 8 phần tử . Giả sử dùng f2 x để xây dựng trường Z2 x x3 x 1 . 8 phần tử của trường là 8 đa thức 0 1 x x 1 x2 x2 1 x2 x x2 x 1 Để tính tích của hai phần tử của trường nhân hai đa thức với nhau và rút gọn theo modulo x3 x 1 tức chia cho x3 x 1 và tìm đa thức dư . Vì ta chia một đa thức bậc 3 nên đa thức dư có bậc nhiều nhất là 2 và vì thế nó là một phần tử của trường. Ví dụ ta hãy tính x2 1 x2 x 1 trong Z2 x x3 x 1 . Trước hết tính tích trong Z2 x là x4 x3 x 1. Khi chia cho x3 x 1 ta nhận được biểu thức sau x4 x3 x 1 x 1 x3 x 1 x2 x Bởi vậy trong trường Z2 x x3 x 1 ta có x2 1 x2 x 1 x2 x Trang 21 Vietebooks Nguyễn Hoàng Cương Dưới đây sẽ đưa ra bảng dầy đủ cho cá phần tử khác 0 của trường. Để đơn giản ta viết đa thức a2x2 a1x a0 theo bô ba được sắp a2a1a0. 001 010 011 100 101 110 111 001 001 010 011 100 101 110 111 010 010 100 110 011 001 111 101 011 011 110 101 111 100 001 010 100 100 011 111 110 010 101 001 101 101 001 100 010 111 011 110 110 110 111 001 101 011 010 100 111 111 101 010 001 110 100 011 Việc tính các phần tử nghịch đảo được tực hiện theo thuật toán Euclide mở rông có biến đổi đôi chút. Cuối cùng ta thâý rằng nhóm nhân của các đa thức khác 0 trong trường là môt nhóm cyclic cấp 7. Vì 7 là số nguyên tố nên suy ra mọi phần tử khác 0 của trường đều là phần tử sinh của nhóm này tức là phần tử nguyên thuỷ