CHƯƠNG 1
CƠ BẢN VỀ ĐẠI SỐ TRỪU TƯỢNG
Các thuật toán mật mã thực hiện biến đổi tin tức dưới dạng các số hoặc các phần tử trong không gian
hữu hạn. Khi đó các phép mã và giải mã, thực hiện biến đổi tin tức từ một dạng này sang một dạng khác
cần phải có đặc tính đóng (closure property) trong không gian hữu hạn. Tuy nhiên các toán tử số học
thông thường trên các số – phép cộng, trừ, nhân, chia – không có các đặc tính này. Vì lý do này, các thuật
toán mật mã hoạt động trong không gian hữu hạn để biến đổi tin tức, như đã biết, không chỉ dẫn tới các
toán tử số học thông thường. Mà chúng làm việc trong không gian có các cấu trúc đại số riêng biệt, để
bảo đảm đặc tính đóng.
Trong chương này, sẽ khảo sát về đại số trừu tượng (abstract algebra), nó là một ngành toán học liên
quan đến việc nghiên cứu các cấu trúc đại số như nhóm, vành, trường, hay các cấu trúc tổng quát khác và
nó có vai trò quan trọng trong mật mã hiện đại.
1.1 NHÓM
1.1.1 Nhóm
Định nghĩa 1.1 .1 (Nhóm)
Nhóm (G,
°
) là một tập hợp G cùng với một phép toán hai ngôi, ký hiệu
°
(là một ánh xạ từ tập G × G
→ G) thỏa mãn các tiên đề sau:
G1. Tính đóng: Nếu a, b ∈ G, thì a
°
b ∈ G.
G2. Tính kết hợp: (a
°
b)
°
c = a
°
(b

°
a, có:
o a
-1
°
a = a
-1
°
a
°
e (theo G3)
o a
-1
°
a
°
e = a
-1
°
a
°
(a
-1
°
(a
-1
)
-1
) (theo G4, a
-1

= a
-1
°
e
°
(a
-1
)
-1
(theo G2 và G4)
o a
-1
°
e
°
(a
-1
)
-1
= a
-1
°
(a
-1
)
-1
= e (theo G3 và G4)
⇒ a
-1
°

1
o a
°
e = a (theo G3)
⇒ e
°
a = a
Định lý 1.1.3: Với ∀a, b ∈ G, tồn tại duy nhất x ∈ G sao cho a
°
x = b.
Chứng minh: Chắc chắn, tồn tại ít nhất một phần tử x như vậy, chẳng hạn đặt x = a
-1
°
b, thì x ∈ G
(theo G1) và do đó:
o a
°
x = a
°
(a
-1
°
b) (thế x)
o a
°
(a
-1
°
b) = (a
°

x
o (a
-1
°
a)
°
x = a
-1
°
(a
°
x)
o a
-1
°
(a
°
x) = a
-1
°
b
⇒ x = a
-1
°
b
Định lý 1.1.4: Phần tử đơn vị của một nhóm (G,
°
) là duy nhất.
Chứng minh: Giả sử G có hai phần tử đơn vị là e và f. Vậy thì e
°

k = e
°
k = k (các đẳng thức nhận được theo G3, G4, G2, định lý 1.1.1 và định lý 1.1.2, theo thứ tự).
Như vậy, có thể nói phần tử nghịch đảo của một phần tử x, thay vì một phần tử nghịch đảo.
Định lý 1.1.6: Với ∀a ∈ (G,
°
), (a
-1
)
-1
= a.
Chứng minh: Ta có a
-1
°
a = e, đi đến kết luận dựa vào định lý 1.1.4.
Định lý 1.1.7: Với ∀a, b∈ (G,
°
), (a
°
b)
-1
= b
-1
°
a
-1
.
Chứng minh: Ta có (a
°
b)

x = a
°
y, thì x = y và nếu x
°
a = y
°
a, thì x = y.
Chứng minh:
Nếu a
°
x = a
°
y thì:
o a
-1
°
(a
°
x) = a
-1
°
(a
°
y)
o (a
-1
°
a)
°
x = (a

o x
°
(a
°
a
-1
) = y
°
(a
°
a
-1
)
o x
°
e = y
°
e
⇒ x = y
Ví dụ 1.1.1 (Nhóm)
1. Tập số thực (R) là một nhóm dưới phép cộng (+):
a. Tổng của hai số thực bất kỳ là một số thực (tính đóng).
b. Với
∀
a, b, c
∈
R: (a + b) + c = a + (b + c) (tính kết hợp).
c. Với
∀
a

= {0, 1, 2, 3, 4} là một nhóm theo phép cộng modulo 5. Vì theo bảng tính toán dưới đây,
nó hoàn toàn thỏa mãn 4 tiên đề của nhóm.
+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
4. Tương tự có thể chứng minh rằng tập Z
n
= {0, 1, 2, 3, …, n – 1} là nhóm đối với phép cộng theo
modulo n, ký hiệu
+
n
Z
.
Định nghĩa 1. 1. 2 (Nhóm hữu hạn và vô hạn)
Nhóm G gọi là hữu hạn nếu như tập G có số lượng phần tử hữu hạn, và trường hợp ngược lại gọi là
vô hạn.
Định nghĩa 1.1.3 (Nhóm abel hay nhóm giao hoán)
Nhóm G gọi là giao hoán nếu như với ∀a, b ∈ G thì a
°
b = b
°
a.
Nói cách khác, nhóm abel là nhóm giao hoán. Sau này sẽ không khảo sát các nhóm không giao hoán,
vì vậy mọi nhóm đều là nhóm abel, cho nên thuật ngữ “abel” thường bỏ qua.
Ví dụ 1.1.2
1. Tập hợp của các số nguyên Z là nhóm đối với toán tử (+), tức là cặp (G, +) – là nhóm, ở đây e = 0
và a

1.1.2 Nhóm con
Định nghĩa 1. 1. 5 (Nhóm con)
Một tập con H của G được gọi là một nhóm con của một nhóm (G,
°
) nếu H thỏa mãn các tiên đề về
nhóm và sử dụng cùng các toán tử
°
. Như vậy, nếu H là một nhóm con của (G,
°
), thì (H,
°
) cũng là một
nhóm, và đồng thời thỏa mãn các định lý trên. Kí hiệu
GH ⊆
.
Ví dụ 1.1.3 (Nhóm con)
1. Đối với phép cộng
CRQZ ⊆⊆⊆
.
2. Tập
{ }
e
là nhóm con của mọi nhóm.
3. Tất cả các nhóm con của
+
6
Z
là {0}, {0, 3}, {0, 2, 4} và chính nó. Các nhóm {0, 1}, {0, 5}
không là nhóm con của
+

°
e = h; do đó theo định lý 1.1.4, e
H
= e.
Định lý 1.1.10: Nếu H là một nhóm con của G, và h là một phần tử của H, thì nghịch đảo của h trong
H giống với nghịch đảo của h trong G.
Chứng minh: Gọi h và k là các phần tử của H, sao cho h
°
k = e, bởi vì h cũng thuộc G, h
°
h
-1
= e do
đó theo định lý 1.1.5, k = h
-1
.
Định lý 1.1.11: Nếu S là một tập con không rỗng của G, thì S là một nhóm con của G nếu và chỉ nếu
với ∀a, b ∈ S, a
°
b
-1
∈ S.
Chứng minh:
1. Nếu với ∀a, b ∈ S, a
°
b
-1
cũng thuộc S, thì
o e ∈ S, vì a
°

-1
∈ S.
Định lý 1.1.12: Giao của các nhóm con của nhóm G là một nhóm con.
Chứng minh:
1. Gọi {H
i
} là một tập các nhóm con của G, và K = ∩{H
i
}.
2. e là phần tử của mọi H
i
theo định lý 1.1.9, do đó K không rỗng.
3. Nếu h và k là các phần tử của K, thì với ∀i, có:
o h và k ∈ H
i
.
o Theo định lý trước, h
°
k
-1
∈ H
i

o Do đó, h
°
k
-1
∈ ∩{H
i
}.

Định lý 1.1.14: Nếu H là một nhóm con của G, và x, y là các phần tử của G, thì x
°
H = y
°
H, hoặc x
°
H và y
°
H không giao nhau.
Định lý 1.1.15: Nếu H là một nhóm con của G, thì mọi liên tập trái (phải) của H trong G chứa cùng số
phần tử.
Định lý 1.1.16: Nếu H là một nhóm con của G, thì số liên tập trái phân biệt của H bằng với số liên tập
phải phân biệt của H.
Định lý Lagrange: Nếu H là một nhóm con của một nhóm hữu hạn G, thì
GH |##
, tức là số lượng
phần tử của H là ước số của #G.
Chứng minh: Giả sử G là nhóm hữu hạn và H là nhóm con của nó. Nếu G = H, thì điều cần chứng
minh là hiển nhiên đúng.
Giả sử
{ }
n
hhH ,,
1
=
nhỏ hơn nhóm G và giả sử
HGx \∈
. Lúc này tất cả các phần tử của tập
{ }
xhxhHx

,,
1
=
.
Tương tự các phần tử của tập này cũng khác nhau và không trùng với các phần tử của tập
HxH ∪
. Cứ
tiếp tục như thế, nhận kết quả như sau
∪∪∪= HyHxHG
. Từ đây có
|| G
chia hết cho n.
1.1.3 Bậc phần tử của nhóm
Định nghĩa 1.1.8 (Bậc phần tử của nhóm)
Cho G là một nhóm và
Ga ∈
. Bậc của phần tử a là số dương nhỏ nhất
Zi ∈
, thỏa mãn điều kiện
ea
i
=
. Số này ký hiệu là ord(a). Nếu như số i không tồn tại thì a là phần tử có bậc vô hạn.
Chú ý: biểu thức a
i
được sử dụng để chỉ toán tử lặp (a
°
a
°
…

và
*
8
Z
, khi lập bảng lưu tâm chú ý trên, như sau:
Đối với nhóm
+
6
Z
(nhóm với toán tử cộng, e = 0)
a 0 1 2 3 4 5
ord(a
)
1 6 3 2 3 6
Đối với nhóm
*
9
Z
(nhóm với toán tử nhân, e = 1)
a 1 2 4 5 7 8
ord(a
)
1 6 3 6 3 2
Đối với nhóm
*
8
Z
(nhóm với toán tử nhân, e = 1)
a 1 3 5 7
ord(a

6
của nhóm để biến đổi văn bản mã thành văn bản rõ (tức là giải mã). Chúng ta sẽ nghiên cứu hệ mật RSA
sau này.
1.1.4 Nhóm thừa số
Định nghĩa 1.1.9 (Nhóm thừa số)
Cho một nhóm G và nhóm con tách biệt H của G. Nếu định nghĩa tích của hai liên tập g * H và g’ *
H là liên tập g * g’ * H thì tập hợp các liên tập của G theo H với phép nhân đó làm thành một nhóm, gọi
là nhóm thừa số của G theo H, kí hiệu là G/H.
Ví dụ 1.1.5 (Nhóm thừa số) Cho
0>n
là một số nguyên, tập
{ }
,2,,0 nnnZ ±±=
là nhóm con của
Z
tương ứng với phép cộng. Thì có nhóm thừa số:
{ } { }
nZnnZnZnZZxnZxnZZ +−+++=∈+= 1 ,,2,1,0|/
Bởi vì:
nZnZnnZnZn +=+++=+ 11,0
, …
1.1.5 Nhóm vòng
Nói một cách không hình thức, nhóm có biểu diễn vòng, thì được gọi là nhóm vòng (cyclic group).
Các nhóm như thể có nhiều đặc tính rất hấp dẫn và chúng được các ứng dụng rộng rãi trong mật mã học.
Định nghĩa 1.1.10 (Nhóm cyclic, phần tử sinh của nhóm)
Nhóm G gọi là nhóm cyclic, nếu như tồn tại phần tử
Ga ∈
, sao cho đối với ∀
Gb∈
tồn tại số nguyên

3.
{ }
><== 36,5,4,3,2,1
*
7
Z
4. Nhóm
{ }
7,5,3,1
*
8
=Z
không là nhóm cyclic
5. Cũng dễ dàng chứng minh được rằng nhóm nhân
*
p
Z
với p là số nguyên tố là một nhóm
cyclic.
6. Với
3≥p
là số nguyên tố, thì nhóm
*
n
p
Z
là nhóm cyclic với ∀
1≥n
Không chỉ phần tử đơn vị mà các phần tử khác của nhóm cũng có những tính chất đặc biệt. Một trong
các tính chất đó là “khoảng cách” đến phần tử đơn vị.

*
n
Z
được gọi là nhóm nhân với toán tử nhân của nhóm, bao gồm các phần tử là số nguyên
dương, nhỏ hơn n và nguyên tố cùng nhau với n. Nhóm này bao gồm
φ
(n) = (p – 1)(q – 1) phần tử.
Nhóm này có nhiều ứng dụng trong lý thuyết số và mật mã học. Đặc biệt là việc tìm bậc của nhóm
giúp kiểm tra tính nguyên tố của n. Nếu như bậc của nhóm là n –1 thì n là số nguyên tố.
Ví dụ 1.1.7
1. Cho nhóm
*
5
Z
, các phần tử của nhóm là 1, 2, 3, 4. Bậc của nhóm là 4. nên 5 là số nguyên tố.
2. Cho nhóm
*
10
Z
, các phần tử của nhóm là 1, 3, 7, 9. Bậc của nhóm là 4, nên 10 không phải là số
nguyên tố.
1.1.7 Đồng hình, đẳng cấu
Định nghĩa 1.1.13 (Đồng hình (homomorphism), đẳng cấu (isomorphism))
Giả sử G
1
và G
2
là các nhóm, ⋅ và ∗ là các toán tử tương ứng trong các nhóm này. Ánh xạ f: G
1
→ G

+
R
(gồm các số thực dương) trong nhóm cộng
+
R
(gồm các số
thực) được thực hiện dưới dạng sau:
log:
*
+
R
→
+
R
log xy = log x + log y, x, y ∈
+
R

2. Phép đồng hình của nhóm cộng
+
R

+
R
(gồm các số thực) trong nhóm nhân
*
+
R
(gồm các số thực
dương) được thực hiện dưới dạng sau:

theo quy tắc
i
i 2
2. Tương tự đối với nhóm
{ }
6,5,4,3,2,1
*
7
=Z
cũng thành lập được sự đẳng cấu
*
76
ZZ 
+
theo
quy tắc
i
i 3
Chú ý: phép ánh xạ trong 2 thí dụ trên có hoán vị một vài số hạng !
1.2 VÀNH
1.2.1 Vành
Định nghĩa 1.2.1 (Vành)
Vành (R, +, ∗) chứa tập R với hai phép toán hai ngôi (được ký hiệu là + (cộng) và ∗ (nhân)) thỏa mãn
các tiên đề sau:
R1. (R, +) là một nhóm giao hoán đối với phép cộng. Phần tử đơn vị đối với phép cộng (không) được
ký hiệu 0.
R2. Phép ∗ có tính phân phối đối với phép +, nghĩa là:
acabacb
cabacbaRcba
∗+∗=∗+

Định lý 1.2.1: Giao của các vành con của R là vành con của R.
9
Định nghĩa 1.2.5 (Vành thừa số)
o Cho A là một ideal của vành R và phần tử x
∈
R. Tập con của R gồm các phần tử dạng x + a
với ∀a
∈
A được gọi là một liên tập của A theo x.
o Ký hiệu R/A là tập hợp tất cả các liên tập của A với ∀x
∈
R: R/A = {x + A| x
∈
R} được gọi
là tập thừa số của R theo A.
o Trên tập thừa số R/A có thể xác định hai phép toán cộng và nhân như sau:
 (x + A) + (y + A) = (x + y) + A
 (x + A) * ( y + A) = (x * y) + A
Khi đó có thể chứng minh R/A là một vành, và vành này được gọi là vành thừa số của R theo A.
1.2.2 Một số khái niệm về ideal
Trong lý thuyết vành, ideal là một tập con đặc biệt của một vành.
1. Vành con A của vành R được gọi là ideal trái (hoặc phải) của R nếu x ∗ a
∈
A (hoặc a ∗ x
∈
A)
với ∀a
∈
A, với ∀x
∈

.
1.3 TRƯỜNG
1.3.1 Trường
Đị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)
1. 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.
2. Tập Z
p
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)
10
1. 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.
2. Tập A ⊆ R:
{ }
QbabaA ∈+= ,|2
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

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
F
, 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
p
Z
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
n
pq =
,
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.
11
Định lý 1.3.1: Nhóm nhân
*
n
Z
của các phần tử không âm của một trường hữu hạn
q
F
là nhóm cyclic.
Phần tử sinh
α

–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
4
F
. 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

, còn x là ký hiệu, không thuộc trường
q
F
.
Hệ số
n
a
có bậc cao nhất và không bằng không khi
0>n
. Số nguyên n gọi là bậc của đa thức
)(xf
được
ký hiệu
)deg())(deg( fxfn ==
. Nếu hệ số cao nhất bằng
0
a
, thì đa thức f gọi là hằng số. Nếu hệ số cao
nhất bằng
0
0
=a
, 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
q
F
ký hiệu là
[ ]
xF
q
Chú ý: Việc cộng, trừ, nhân chia đa thức thuộc

Định lý 1.3.3: Cho F là một trường, còn
)(xf
là đa thức khác không từ tập
[ ]
xF
. Khi đó tập
[ ]
)(/ xfxF
là một trường khi và chỉ khi
)(xf
là đa thức bất khả quy trên trường F.
Chứng minh. Thứ nhất, tập
[ ]
)(/ xfxF
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ử
[ ]
)(/ xfxF
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
[ ]
xF
, không là hằng số. Lúc này, bởi vì
)deg()deg(0 fg <<
và
)deg()deg(0 fh <<
, các đa thức g và h không là hằng số trong tập
[ ]
)(/ xfxF

này
[ ]
)(/, xfxFsFc ∈∈
và
1),gcd( =sf
. Có thể tính
[ ]
)(/)(mod
1
xfxFfs ∈
−
. Ngoài ra bời vì
Fc ∈
,
nên tồn tại
Fc ∈
−1
. Như vậy nhận được phần tử
[ ]
)(/
111
xfxFscr ∈=
−−−
.
Chú ý:
)(xf
thường gọi là đa thức xác định của trường
[ ]
)(/ xfxF
.

trường hữu hạn 4 phần tử.
2. Xây dựng
8
F
=
[ ]
)1/(
23
2
++ xxxF
, bởi vì
1
23
++ xx
là đa thức bất khả quy trong trường
2
F
. Các
phần tử của trường là 0, x, x, x + 1,
2
x
,
1
2
+x
,
xx +
2
,
1

4
+ x
3
+ 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 = a
1
a
2
…a
n
, ở đây a
1
, a
2
,…,
a
n
2
F∈
.
Thì đa thức biểu diễn có dạng:
nn
nn
axaxaxaxf ++++=
−
−−
1
2
2
1

14
Định lý 1.3.5: Cho F là một trường hữu hạn, còn
[ ]
xFf ∈
là đa thức bất khả quy bậc n trên trường F.
Nếu như
θ
là một nghiệm bất kỳ của
0)( =xf
, thì các phần tử
12
, ,,,1
−n
θθθ
là độc lập tuyến tính trên
trường F, có nghĩa là đối với
Fr
i
∈
, với
1 ,,2,1,0 −= ni
,
0
1
1
2
210
=++++
−
−

2
210
=++++=
−
−
n
n
xrxrxrrxr
Nếu như
)1 ,,2,1,0( −=∈ niFr
i
, thì rõ ràng
)(xr
thuộc trường
[ ]
)(/ xfxF
. Dẫn đến điều kiện
0)( =xr
, tương đương với
)(mod0)( xfxr ≡
. Giả sử
n
a
là hệ số bậc cao của f(x). Khi đó
0, ≠∈
nn
aFa
và
)(|)(
1

có cấu trúc sau:






∈
∑
−
−
=
Frrrr
n
n
i
i
i 110
1
0
, ,,
θ
.
Định lý 1.3.6: Cho F là trường hữu hạn,
)(xf
là đa thức bất khả quy bậc n trên trường F. Không gian
vector (định nghĩa 1.3.10) đối với bất kỳ nghiệm
θ
nào của phương trình
)(xf

n
nn
n
−−−=
−
−
−

θθ
.
Nhờ vậy mà
n
θ
là tổ hợp tuyên tính của đa thức cơ sở
12
, ,,,1
−n
θθθ
. Nhân hai vế của f(
θ
) cho
θ
, dễ
dàng chứng tỏ rằng với bất kỳ một số nguyên dương
nm ≥
, phần tử
m
θ
có thể biểu diễn dưới dạng tổ
hợp tuyến tính của chính đa thức cơ sở của nó. Điều này dẫn đến, bất kỳ phần tử u, v từ không gian (định

q
F
)
Cho q là số lượng phần tử của trường hữu hạn F. Ký hiệu
n
q
F
cho trường hữu hạn, được xây dựng
trên cơ sở gồm n phần tử trên trường F.
Ví dụ 1.3.5 (Trường
8
2
F
)
Thấy rằng
[ ]
xF
2
/ x
8
+ x
4
+ x
3
+ x + 1 là một trường bao gồm 2
8
phần tử. Biết rằng
8
2
F

7
, b
6
, b
5
, b
4
, b
3
, b
2
, b
1
, b
0
2
F∈
.
Nhận thấy việc tính toán trong trường
8
2
F
đơn giản hơn trong trường
[ ]
xF
2
/ x
8
+ x
4

4
+ α
3
+ 1
Bởi vì α
8
+ α
4
+ α
3
+ α + 1 = 0 nên nhận được các tổ hợp tuyến tính sau:
α
8
= α
4
+ α
3
+ α + 1
α
9
= α
5
+ α
4
+ α
2
+ α
α
11
= α

4
+ α
3
+ 1= α
7
+ α
6
+ 1. Và có nghĩa là ‘57’.’83’=’C1’. Nếu như dùng
[ ]
xF
2
/ x
8
+x
4
+x
3
+x+1, thì cần phải thực hiện phép chia và sẽ phức tạp hơn.
Định lý 1.3.7: Cho F là trường hữu hạn bao gồm q phần tử, còn
n
q
F
là trường hữu hạn xây dựng trên
đa thức cơ sở trường F. Khi đó
1. Trường F là trường con của trường
n
q
F
2. Bất kỳ thành phần
n

là nhóm nhân với các phần tử khác không. Như vậy điều kiện
Fa ∈

có thể là 0 hoặc có thể là thuộc
*
F
. Với khả năng đầu tiên thì điều kiện
aa
q
=
là hiển nhiên đúng. Đối
với khả năng thứ hai, nhóm sinh bởi phần tử sinh a, rõ ràng nhóm này là nhóm con của
*
F
, thì theo định
lý Lagrange có (a)|#
*
F
= q – 1, và có
1
1
=
−q
a
. Nhờ vậy mà
aa
q
=
.
Chứng minh điều ngược lại: Bất kỳ phần tử a thuộc

không là phần tử của
n
q
F
.
1.4 XÂY DỰNG NHÓM TRÊN CƠ SỞ ĐƯỜNG CONG ELLIPTIC
Các nhóm xây dựng trên cơ sở đường elliptic (elliptic curves) đóng vai trò rất quan trọng trong mật
mã hiện đại. Ứng dụng của các nhóm này trong mật mã khóa công khai, được đề xuất đầu tiên bởi hai nhà
khoa học Neal Koblitz và Victor S. Miller.
1.4.1 Công thức Weierstrasse và đường cong elliptic
Gọi K là một trường hữu hạn hoặc vô hạn. Một đường cong elliptic được định nghĩa trên trường K
bằng công thức Weierstrass:
y
2
+ axy + by = x
3
+ cx
2
+ dx + e,
ở đây a, b, c, d, e là các số thỏa mãn một vài điều kiện đơn giản nào đó và thuộc K.
Hình 1: Các ví dụ về đường cong elliptic
1.4.2 Đường cong elliptic trên trường hữu hạn
Đường cong elliptic được xây dựng trên các trường hữu hạn. Có hai trường hữu hạn thường được sử
dụng: trường hữu hạn F
q
với q là số nguyên tố p hoặc q là 2
m
(m là số nguyên).
17
Tùy thuộc vào trường hữu hạn F

+ ax + b,
cùng với điểm O đặc biệt gọi là điểm vô cực và có thể biểu diễn dưới dạng O = (x,
∞
).
Số lượng điểm của E(F
p
) là #E(F
p
) thỏa mãn định lý Hasse.
Chú ý: Độ phức tạp của thuật toán xây dựng trên nhóm đường cong Elliptic phụ thuộc vào số điểm
trên đường cong đó, và xét định lý Hasse về số điểm trên đường cong Elliptic.
Định lý 1.4.1 (Định lý Hasse): Số các điểm trên đương cong Elliptic thỏa mãn bất đẳng thức sau:
ppFEpp
p
21)(#21 ++≤≤−+
.
Định nghĩa 1.4.2 (Bậc của điểm)
Cho điểm P(x, y) thuộc đường cong elliptic. Bậc n của điểm P(x, y) là số nguyên dương thỏa mãn
biểu thức:
OnP =
.
Tập hợp các điểm trên E(F
p
) tạo thành một nhóm thỏa mãn các tính chất sau:
o Tính đóng: ∀a, b ∈ G, a + b ∈ G.
o Tính kết hợp: Các phép toán trong nhóm có tính kết hợp.
Do đó, (a + b) + c = a + (b + c).
o Phần tử đơn vị: có một giá trị 0 ∈ G sao cho a + 0 = 0 + a = a, ∀a ∈ G.
o Phần tử nghịch đảo: ∀a ∈ G,
∃

Đối với các nhóm điểm trên elliptic chỉ khảo sát các giá trị nguyên từ (0, 0) đến (p, p) trong góc phần tư
của các số không âm (góc thứ nhất), phù hợp với phương trình theo modulo p.
18
Hình 2: Đường cong elliptic y
2
= x
3
+ x +1
Trong bảng dưới, trình bày các điểm (khác với O) là các phần tử của trường E
23
(1, 1).
(0, 1) (6, 4) (12, 19)
(0, 22) (6, 19) (13, 7)
(1, 7) (7, 11) (13, 16)
(1, 16) (7, 12) (17, 3)
(3, 10) (9, 7) (17, 20)
(3, 13) (9, 16) (18, 3)
(4, 0) (11, 3) (18, 20)
(5, 4) (11, 20) (19, 5)
(5, 19) (12, 4) (19, 18)
4.2.2 Đường cong elliptic trên trường
m
F
2
Định nghĩa 1. 4. 3 (Đường cong elliptic trên trường
m
F
2
)
Một đường cong elliptic E(

qqFEqq
q
21)(#21 ++≤≤−+
trong đó p = 2
m
. Ngoài ra, #E(
m
F
2
) là số chẵn.
Tập hợp các điểm trên E(
m
F
2
) tạo thành một nhóm thỏa mãn các tính chất sau:
o O + O = O.
o (x, y) + O = (x, y), ∀(x, y) ∈ E(
m
F
2
)
o (x, y) + (x, - y) = O, ∀(x, y) ∈ E(
m
F
2
). Khi đó, (x,- y) là điểm đối của (x, y) trên E(
m
F
2
).