Định nghĩa 1.3.1 (Trường) Nếu các phần tử khác không của vành tạo thành nhóm tương ứng với phép nhân thì gọi vành đó là trường.
Ví dụ 1.3.1 (Trường)
-
Tập Q, R và C là trường tương ứng với phép cộng và nhân thông thường, với phần tử 0 là 0 và phần tử 1 là 1.
-
Tập Zp với với p là số nguyên tố là trường tương ứng với phép cộng và nhân cho modulo p, với phần tử 0 là 0 và phần tử 1 là 1.
Định nghĩa 1.3.2 (Trường con)
Giả sử F là một trường. Tập con E F được gọi là trường con của F nếu chính E là một trường với cùng phép toán trong F.
Ví dụ 1.3.2 (Trường con)
-
Trường số hữu tỷ Q là trường con của trường số thực, R trường số thực là trường con của trường số phức C.
-
Tập A R: là trường con của R.
Trên thực tế, đôi khi không nhất thiết phân chia ra thành nhóm, vành và trường. Trong tình huống như thế chúng được gọi là các cấu trúc đại số (algebraic structure).
Định nghĩa 1.3.3 (Cấu trúc đại số)
Cấu trúc đại số được gọi là hữu hạn, nếu nó bao gồm số lượng hữu hạn các phần tử. Số lượng các phần tử của cấu trúc hữu hạn được gọi là bậc của nó.
Tập con không rỗng S, mà nó có cấu trúc đại số tương ứng đối với các toán tử đã được định nghĩa trong cấu trúc A được gọi là cấu trúc con của cấu trúc đại số A. Nếu S A, thì cấu trúc con S được gọi là cấu trúc con riêng biệt của cấu trúc A.
Giả sử A – cấu trúc đại số, còn B A – cấu trúc con của A. Tập hợp của tất cả các liên tập a ° B, ở đây phần tử a lấy theo tất cả cấu trúc A, đối với toán tử , được xác định theo quy tắc (a ° B) (b ° B) = (a ° b) ° B, với các phần tử không 0 ° B và 1 ° B được gọi là cấu trúc thừa số của A theo modulo B, ký hiệu A/ B.
Từ định nghĩa 1.3.3 thấy rằng vành (trường tương ứng) có thể chứa không chỉ vành con (trường con tương ứng), mà cả nhóm con (vành con và nhóm con tương ứng).
-
Trường hữu hạn
Trường hữu hạn là trường được ứng dụng rất nhiều trong mật mã, bởi vậy phần này sẽ đi sâu khảo sát một số phương pháp xây dựng một trường hữu hạn cũng như các tính chất của chúng.
-
Các trường hữu hạn, bao gồm các phần tử nguyên tố
Các trường hữu hạn mà bậc của chúng (số lượng các phần tử) là số nguyên tố có cấu trúc đơn giản nhất. Các trường như vậy được ứng dụng rộng rãi trong mật mã.
Định nghĩa 1.3.4 (Trường nguyên tố)
Trường, không bao gồm các trường con riêng biệt, được gọi là trường nguyên tố.
Chẳng hạn, trường Q – trường nguyên tố, còn tập hợp R – không, bởi vì tập hợp Q là trường con riêng biệt của trường R. Tuy nhiên, Q là trường vô hạn. Chúng ta sẽ khẳng định sau này, trường nguyên tố hữu hạn bao gồm số nguyên tố của các phần tử, tức là bậc của nó là số nguyên tố.
Định nghĩa 1.3.5 (Trường hữu hạn)
Trường F gọi là trường hữu hạn, nếu như số phần tử của nó là hữu hạn, ký hiệu là , q là số phần tử của trường hữu hạn.
Chú ý: Ở trên đã biết rằng, nếu p là số nguyên tố thì vành là một trường, nhưng trên thực tế có nhiều trường hữu hạn khác không có dạng trên. Ví dụ, xây dựng trường hữu hạn q phần tử, với , với p là số nguyên tố, và n 1 là số nguyên, một trường hữu hạn có số nguyên phần tử như vậy gọi là trường Galois.
Định lý 1.3.1: Nhóm nhân của các phần tử không âm của một trường hữu hạnlà nhóm cyclic. Phần tử sinh của nhóm cyclic gọi là phần tử nguyên thủy của trường hữu hạn . Tất cả các phần tử của trường hữu hạn có thể viết dưới dạng sau:
Định nghĩa 1.3.6 (Đồng hình và đẳng cấu)
Giả sử A và B – các cấu trúc đại số. Ánh xạ f: A B được gọi là đồng hình từ cấu trúc A vào cấu trúc B, nếu ánh xạ f bao gồm các toán tử đã được định nghĩa trong cấu trúc A. Nói một cách khác, nếu ° – toán tử được định nghĩa trong cấu trúc A, còn – toán tử được định nghĩa trong cấu trúc B, thì x, y A: f(x ° y) = f(x) f(y). Phép biến đổi đồng hình là song ánh f từ cấu trúc A lên cấu trúc B được gọi là đẳng cấu, còn các cấu trúc A và B – đẳng cấu.
Nếu f: A B là đồng hình, còn e – phần tử đơn vị của cấu trúc A (tương ứng với phép cộng và phép nhân), thì:
f(e) f(e) = f(e ° e) = f(e).
Tiếp theo, phần tử f(e) là phần tử đơn vị của cấu trúc B. Ngoài ra, đối với bất kỳ a A
f(a) f(a–1) = f(a ° a–1) = f(e),
bởi vì f(a–1) = f(a)–1 đối với tất cả a A. Hơn nữa, nếu các cấu trúc A và B là đẳng cấu, chúng bao gồm cùng số lượng phần tử. Như vậy, hai cấu trúc đẳng cấu được xây dựng như nhau.
Định nghĩa 1.3.7 (Đặc số của cấu trúc đại số)
Đặc số của cấu trúc đại số A, ký hiệu char (A), – là số nguyên dương nhỏ nhất n, sao cho na = 0 đối với phần tử bất kỳ a A. Nếu số nguyên như thế không tồn tại, thì đặc số của cấu trúc A bằng không.
Định lý 1.3.2: Đặc số của trường hữu hạn bất kỳ là số nguyên tố (nếu đặc số không bằng 0).
Ví dụ 1.3.3 Xây dựng trường. Phép cộng và phép nhân của trường được cho bởi 2 bảng tính như sau (xem ví dụ 1.3.4.(1) để biết vì sao có được kết quả của hai bảng này):
+
|
0
|
1
|
2
|
3
|
0
|
0
|
1
|
2
|
3
|
1
|
1
|
0
|
3
|
2
|
2
|
2
|
3
|
0
|
1
|
3
|
3
|
2
|
1
|
0
|
*
|
1
|
2
|
3
|
1
|
1
|
2
|
3
|
2
|
2
|
3
|
1
|
3
|
3
|
1
|
2
| -
Trường hữu hạn xây dựng trên đa thức bất khả quy.
Bậc của trường hữu hạn nguyên tố bằng đặc số của trường đó. Tuy nhiên, trường nguyên tố không thể xem là điển hình. Dạng chung hơn của trường hữu hạn có thể được xây dựng dựa trên các đa thức.
Định nghĩa 1.3.8 (Đa thức trong trường hữu hạn)
Cholà trường hữu hạn. Đa thức xây dựng trên trường được cho dưới dạng sau:
ở đây n là số nguyên không âm, là hệ số, , , còn x là ký hiệu, không thuộc trường . Hệ số có bậc cao nhất và không bằng không khi . Số nguyên n gọi là bậc của đa thứcđược ký hiệu. Nếu hệ số cao nhất bằng , thì đa thức f gọi là hằng số. Nếu hệ số cao nhất bằng , thì đa thức f gọi là đa thức không và ký hiệu f = 0. Tập tất cả các đa thức trên trường ký hiệu là
Chú ý: Việc cộng, trừ, nhân chia đa thức thuộc, giống như cộng, nhân, chia các đa thức bình thường, chỉ khác là tính các hệ số trong trường đã cho.
Định nghĩa 1.3.9 (Đa thức bất khả quy)
Đa thức được gọi là bất khả quy nếu không tồn tại các đa thức sao cho
Trong đó và
Định lý 1.3.3: Cho F là một trường, còn là đa thức khác không từ tập . Khi đó tập là một trường khi và chỉ khi là đa thức bất khả quy trên trường F.
Chứng minh. Thứ nhất, tập rõ ràng là một vành ứng với phép cộng và nhân theo modulo f(x). Phần tử không và phần tử đơn vị tương ứng với phần tử không và phần tử đơn vị của trường F.
Thứ hai, giả sử là một trường, mà f(x) không là đa thức bất khả quy, có nghĩa là có thể đặt f = gh, với g, h là hai đa thức từ tập , không là hằng số. Lúc này, bởi vì và , các đa thức g và h không là hằng số trong tập , mặc dù f là đa thức không trong . Điều này là vô lý. Như vậy không thể là một trường. Điều vô lý này chứng tỏ rằng f không thể là không bất khả quy nếu như là một trường.
Bây giờ xét nếu như đa thức f là bất khả quy trên trường F. Bởi vì là một vành, cần chứng minh rằng đối với một phần tử khác không của tập tồn tại một phần tử nghịch đảo tương ứng với phép nhân. Giả sử r là đa thức khác không từ tập , với . Bởi vì , còn f là bất khả quy, nên đa thức c phải là hằng số. Biểu diễn r dưới dạng . Lúc này và . Có thể tính . Ngoài ra bời vì , nên tồn tại . Như vậy nhận được phần tử .
Chú ý: thường gọi là đa thức xác định của trường.
Ví dụ 1.3.4 (Xây dựng trường hữu hạn trên cơ sở đa thức bất khả quy)
-
Xây dựng trường, với . Các phần tử của trường là: 0, 1, x, x + 1, chọn = x2 + x + 1. Xét xem đây có phải là 1 trường hay không. Lập bảng tính đối với phép cộng và phép nhân:
+
|
0
|
1
|
x
|
x + 1
|
0
|
0
|
1
|
x
|
x + 1
|
1
|
1
|
0
|
x + 1
|
x
|
x
|
x
|
x + 1
|
0
|
1
|
x + 1
|
x + 1
|
x
|
1
|
0
|
*
|
1
|
x
|
x + 1
|
1
|
1
|
x
|
x + 1
|
x
|
x
|
x +1
|
1
|
x + 1
|
x + 1
|
1
|
x
|
Từ 2 bảng trên, khẳng định rằng trên cơ sở đa thức bất khả quy = x2 + x + 1, đã xây dựng được trường hữu hạn 4 phần tử.
-
Xây dựng =, bởi vì là đa thức bất khả quy trong trường. Các phần tử của trường là 0, x, x, x + 1, ,,,. Để đơn giản tính toán, biểu diễn các phần tử của trường thông qua vector cơ số 2 (xem chú ý dưới). Và nhận được bảng tính toán của các phần tử trong trường trên bởi phép nhân
*
|
001
|
010
|
011
|
100
|
101
|
110
|
111
|
001
|
001
|
010
|
011
|
100
|
101
|
110
|
111
|
010
|
010
|
100
|
110
|
101
|
111
|
001
|
011
|
011
|
011
|
110
|
101
|
001
|
010
|
111
|
100
|
100
|
100
|
101
|
001
|
111
|
011
|
010
|
110
|
101
|
101
|
111
|
010
|
011
|
110
|
100
|
001
|
110
|
110
|
001
|
111
|
010
|
100
|
011
|
101
|
111
|
111
|
011
|
100
|
110
|
001
|
101
|
010
| -
Xây dựng một trường 28 phần tử:/ x8 + x4 + x3 + x + 1. Độc giả tự giải. Sau đó thử tính kết quả của phép nhân ‘57’.’F3’. Hướng dẫn tính, đầu tiên biễu diễn ‘57’ và ‘F3’ dưới dạng đa thức, nhân 2 đa thức đó, và thực hiện phép chia modulo cho x8 + x4 + x3 + x + 1.
Chú ý: Một số n bit có thể biểu diễn dưới dạng đa thức bậc n – 1. Ví dụ a = a1a2…an, ở đây a1, a2,…, an. Thì đa thức biểu diễn có dạng: .
Định lý 1.3.4: Cho F là một trường, bao gồm p phần tử, còn f là đa thức bất khả quy bậc n trên trường F. Lúc này số lượng phần tử của trường bằng .
Chứng minh: là tập các đa thức từ tập , bậc của nó nhỏ hơn bậc của đa thức f(x), tức là nhỏ hơn n, còn hệ số của nó thuộc về trường F, bao gồm p phần tử. Nên trường tồn tại phần tử như vậy.
Chia sẻ với bạn bè của bạn: |