ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ






ĐÀO VIỆT ANH








NGHIÊN CỨU MỘT SỐ CHỮ KÝ ĐẶC BIỆT
TRÊN ĐƢỜNG CONG ELLIPTIC








LUẬN VĂN THẠC SĨ

HẢI PHÒNG – 2011
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ






ĐÀO VIỆT ANH






NGHIÊN CỨU MỘT SỐ CHỮ KÝ ĐẶC BIỆT

TRÊN ĐƢỜNG CONG ELLIPTIC


Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60 08 45




LUẬN VĂN THẠC SĨ


Ngƣời hƣớng dẫn khoa học: PGS. TS Trịnh Nhật Tiến









HẢI PHÒNG – 2011

MỤC LỤC

LỜI CAM ĐOAN 1
MỤC LỤC 2
BẢNG DANH MỤC CÁC TỪ VIẾT TẮT 1

DANH MỤC CÁC HÌNH VẼ 2
Chương 1. CÁC KHÁI NIỆM CƠ BẢN 4
1.1. MỘT SỐ KHÁI NIỆM TRONG SỐ HỌC 4
1.1.1. Số nguyên tố 4
1.2. MỘT SỐ KHÁI NIỆM TRONG ĐẠI SỐ 8
1.2.1. Khái niệm Nhóm, Vành, Trƣờng 8
1.2.3. Không gian vector 11
1.2.4. Vành tuyến tính 12
1.2.5. Trƣờng hữu hạn 13
1.3. KHÁI NIỆM VỀ ĐỘ PHỨC TẠP CỦA THUẬT TOÁN 16
1.3.1. Khái niệm thuật toán 16
1.3.2. Độ phức tạp của thuật toán 16
1.3.3 Một số lớp bài toán 18
1.4. MỘT SỐ KHÁI NIỆM TRONG MẬT MÃ 21
1.4.1. Mã hóa 21
1.4.2. Chữ ký số 25
1.4.2.1. Sơ đồ chữ ký số 25
Chương 2. SƠ ĐỒ CHỮ KÝ TRÊN ĐƢỜNG CONG ELLIPTIC 26
2.1.2. Đƣờng cong Elliptic trên trƣờng Galois 27
2.1.3. Đƣờng cong Elliptic trên trƣờng hữu hạn 30
2.1.3.1 Đường cong elliptic trên trường F
P
(p là số nguyên tố) 30
2.1.3.2 Đường cong elliptic trên trường F
2
m
31
2.1.4 CÁC PHÉP TOÁN TRÊN ĐƢỜNG CONG ELLIPTIC 32
2.1.4.1 Phép cộng 32
2.1.4.2 Phép nhân 35

2.1.5 SỐ ĐIỂM TRÊN ĐƢỜNG CONG ELLIPTIC VỚI TRƢỜNG F
Q
38
2.2. MỘT SỐ SƠ ĐỒ CHỮ KÝ TRÊN ĐƢỜNG CONG ELLIPTIC 39
2.2.1 NHÚNG BẢN RÕ VÀO ĐƢỜNG CONG ELLIPTIC 40
2.2.1.1 Phép nhúng (Imbeding) 40
2.2.1.2 Phép mặt nạ (Mask) 41
2.2.2 SƠ ĐỒ CHỮ KÝ TRÊN ĐƢỜNG CONG ELLIPTIC 41
2.2.2.1 Sơ đồ chữ ký ECDSA 41
2.2.2.2 Sơ đồ chữ ký Nyberg - Rueppel 43
2.2.2.3 Sơ đồ chữ ký mù Harn trên EC 43
2.2.2.4 Sơ đồ chữ ký mù bội Harn trên EC 46
2.3. MỘT SỐ PHƢƠNG PHÁP TẤN CÔNG CHỮ KÝ ECC 48
2.3.1. Phƣơng pháp tấn công “baby-step giant - step” 48
2.3.2 Phƣơng pháp tấn công MOV 49
2.3.3. Các thuật toán tấn công khác 52
2.4. LỰA CHỌN ĐƢỜNG CONG ELLIPTIC PHÙ HỢP 52
2.4.1. Trƣờng K 52
2.4.2. Dạng của đƣờng cong elliptic 53
2.4.3 Phƣơng pháp lựa chọn 54
2.5. MỘT SỐ CHUẨN SỬ DỤNG HỆ MẬT ECC 55
Chương 3. CHỮ KÝ ECC TRONG TIỀN ĐIỆN TỬ 58
3.1. THANH TOÁN BẰNG TIỀN ĐIỆN TỬ 58
3.1.1. Khái niệm tiền điện tử 58
3.1.2. Lƣợc đồ giao dịch 59
3.1.3. Phân loại 60
3.1.4. Những đặc điểm của tiền điện tử 61
3.1.4.1 Tính an toàn 61
3.1.4.2 Tính riêng tƣ 62
3.1.4.3 Tính độc lập 62

3.1.4.4 Tính chuyển nhƣợng 62
3.1.4.5 Tính phân chia 63
3.1.4.6 Tính dể sử dụng 63
3.1.4.7 Hình thức thanh toán 63
3.2. MỘT SỐ VẤN ĐỀ VỀ TIỀN ĐIỆN TỬ 64
3.2.1. Vấn đề ẩn danh 65
3.2.2. Vấn đề khai man giá trị đồng tiền 65
3.2.3. Vấn đề tiêu xài một đồng tiền nhiều lần 66
3.3. CHỮ KÝ ECC DÙNG TRONG TIỀN ĐIỆN TỬ 69
3.3.1. Sử dụng chữ ký “mù” nhằm ẩn danh ngƣời dùng tiền điện tử 70
3.3.2. Sử dụng chữ ký "dùng một lần" nhằm tránh tiêu một đồng tiền hai lần 71
3.3.3. Sơ đồ tiền điện tử đề xuất 72
Chương 4. CHƢƠNG TRÌNH MÔ PHỎNG GIẢI THUẬT CHỮ KÝ SỐ TRÊN ĐƢỜNG CONG
ELLIPTIC 79
4.1. Cài đặt hệ điều hành Ubuntu 79
4.2. Cài đặt chƣơng trình mô phỏng sơ đồ chữ ký ECDSA 79
4.3. Tổng quan chƣơng trình 80
4.4 Các chức năng chính của chƣơng trình 80
KẾT LUẬN 84
TÀI LIỆU THAM KHẢO 85
PHỤ LỤC 86

1



BẢNG DANH MỤC CÁC TỪ VIẾT TẮT




Từ viết tắt
Từ gốc
Nghĩa tiếng Việt
DLP
Discrete Logarithm Problem
Vấn đề logarit rời rạc
ECC
Elliptic Curve Cryptography
Hệ mật trên đƣờng cong Elliptic
EDLP
Elliptic Curve Discrete Logarithm
Problem
Vấn đề logarit rời rạc trên đƣờng
cong Elliptic
MD5
Message Digest Algorithm 5
Thuật toán tạo "vết" 5
TOF
Trap Door One-Way Function
Hàm cửa sập một chiều
RFC
Request for Comments

Yêu cầu bình luận
SHA
Secure Hash Algorithm
Thuật toán "băm" an toàn
1
2
2

3 DANH MỤC CÁC HÌNH VẼ

Hình vẽ
Tên hình vẽ
Hình 2.1
Một ví dụ về đƣờng cong elliptic
Hình 2.2
Điểm ở vô cực
Hình 2.3
Phép cộng trên đƣờng cong elliptic
Hình 2.4
Phép nhân đôi trên đƣờng cong elliptic
Hình 3.1
Mô hình giao dịch cơ bản của hệ thống tiền điện tử
Hình 3.2
Phân loại tiền điện tử
Hình 3.3
Mô hình giao dịch có tính chuyển nhƣợng
Hình 4.1
Giao diện quá trình sinh khóa
Hình 4.2
Giao diện quá trình ký
Hình 4.3
Giao diện quá trình giải mã

3
LỜI MỞ ĐẦU

Hiện nay sự ứng dụng công nghệ thông tin trong đời sống ngày càng lớn. Với
sự phát triển của các thiết bị cầm tay với ƣu điểm tiện lợi, linh hoạt thì nhu cầu xây

dựng những ứng dụng trên các thiết bị này ngày càng lớn.
Một trong những đặc điểm của các thiết bị cầm tay là bộ nhớ nhỏ với tốc độ
tính toán thấp. Chính vì vậy xuất phát từ thực tế đó, các thuật toán mã hóa trên đƣờng
cong Elliptic với ƣu điểm là tốc độ xử lý nhanh, không cần nhiều tài nguyên đã ra đời
và rất thích hợp với các thiết bị cầm tay này vì nó vừa đảm bảo độ an toàn và không
yêu cầu nhiều tài nguyên. Chính vì vậy em đã chọn đề tài:" Nghiện cứu một số chữ ký
đặc biệt trên đƣờng cong Elliptic" làm đề tài luận văn thạc sĩ của mình.
Nội dung của đề tài:
Chương 1: Một số khái niệm cơ bản
Nêu lên một số khái niệm cơ bản về đại số, số học, các khái niệm về mã hóa,
chữ ký số cũng nhƣ độ phức tạp thuật toán.
Chương 2: Sơ đồ chữ ký trên đường cong Elliptic
Nêu lên một số sơ đồ chữ ký số đặc biệt trên đƣờng cong Elliptic
Chương 3: Chữ ký ECC trong tiền điện tử
Nêu lên những ứng dụng của chữ ký số trên đƣờng cong Elliptic(ECC) trong
các hệ thống tiền điện tử,
Chương 4: Xây dựng chương trình mô phỏng giải thuật chữ ký số trên
đường cong Elliptic
Xây dựng một chƣơng trình nhỏ nhằm mô phỏng một sơ đồ chữ ký số trên
đƣờng cong Elliptic (ECDSA- Elliptic curve digital signature algorithm).
Em xin chân thành cảm ơn PGS.TS Trịnh Nhật Tiến đã giúp đỡ em trong suốt
quá trình viết luận văn này.
4
Chương 1. CÁC KHÁI NIỆM CƠ BẢN
1.1. MỘT SỐ KHÁI NIỆM TRONG SỐ HỌC
1.1.1. Số nguyên tố
Số nguyên a > 1 đƣợc gọi là số nguyên tố, nếu a chỉ có ƣớc số là 1 và a.
Một số nguyên lớn hơn 1 không là số nguyên tố thì đƣợc gọi là hợp số.
Ví dụ các số 2, 3, 5, 7 là số nguyên tố; các số 6, 8, 10, 12, 14, 15 là hợp số.
Hai số a và b đƣợc gọi là nguyên tố cùng nhau, nếu chúng có ƣớc số chung là 1,

tức là nếu gcd (a,b) = 1.
Một số nguyên n > 1 bất kỳ đều có thể viết dƣới dạng
n = p
1
a1
. p
2
a2
p
k
ak

trong đó p
1
, p
2
, ,p
k
là các số nguyên tố khác nhau, a
1
, a
2
, a
k
là các số mũ
nguyên dƣơng.
Nếu không kể thứ tự các thừa số nguyên tố thì dạng biểu diễn đó là duy nhất, ta
gọi đó là dạng khai triển chính tắc của n. Ví dụ dạng khai triển chính tắc của 1800 là
2
3

3
2
5
2
.
Các số nguyên tố và các vấn đề về số nguyên tố có một vai trò quan trọng trong
số học và trong ứng dụng vào lý thuyết mã hóa, sẽ xét riêng trong chƣơng sau.
Định lý 1.1 (Thuật toán Euclid tìm ƣớc số chung lớn nhất)
Với mọi a, b

Z, b

0, tồn tại duy nhất q, r

Z để: a = bq + r,
0 | |rb

Nếu r = 0 thì b|a, nghĩa là b là ƣớc số của a.
Ngƣợc lại thì b a. Với a
1
, …, a
k


Z, nếu b|a
i
(i = 1,…, k) thì b gọi là ƣớc
chung của a
1
,…,


a
k.
.

Ƣớc chung lớn nhất của a
1
, …, a
k
ký hiệu là gcd(a
1
, …, a
k
) .


5
Định lý 1.2
Nếu a, b

Z và khác 0 thì d = gcd(a, b) là phần tử nhỏ nhất trong tất cả các số
nguyên dƣơng có dạng ax + by (x, y

Z)
Chứng minh
Giả sử C = {c

N | c = ax + by, x, y

Z}. C


ф. Đặt
e = ax
0
+ by
0

là phần tử nhỏ nhất của C. Chúng ta cần chỉ ra d = e. Nếu a = eq + r,
er 0
thì:
r = a – eq = a(1 – qx
0
) + b(-qy
0
)
Nếu r

0 thì nó phải thuộc C và điều này mâu thuẫn với lựa chọn e. Vì vậy, e|a.
Tƣơng tự, e|b; do đó e

d. Mặt khác, e = ax
0
+ by
0
và d|a, d|b, suy ra d|e.
Vì vậy, d

e. Kết luận, d = e.
Hệ quả 1.3
Tồn tại x, y


Z thỏa mãn:
ax + by = c
khi và chỉ khi d|c với d = gcd(a, b)
Chứng minh
Nếu a = ed, b = fd, thì rõ ràng d|c. Mặt khác nếu d|c, đặt kd = c. Vì tồn tại x
0
, y
0


Z để ax
0
+ by
0
= d, nên a(kx
0
) + b(ky
0
) = kd = c.
Với mọi a, b, m

Z ta định nghĩa
a

b mod m khi và chỉ khi m|(a - b)
Dễ nhận thấy, với m cố định, đây là một quan hệ tƣơng đƣơng trên Z. Vì vậy, Z đƣợc
phân hoạch thành các lớp tƣơng đƣơng: Z
m
= {[a] | a


Z}, với [a] = {b

Z | a

b
mod m}. Mỗi lớp tƣơng đƣơng [a] đƣợc thể hiện bằng các phần tử của nó. Ví dụ, Z
m
=
{0, 1, 2, …, m – 1}.



6
Định lý 1.4
Với a, m

Z, tồn tại x

Z thỏa mãn ax

1 mod m khi và chỉ khi gcd(a, m) = 1.
Chứng minh
x

Z để ax

1 mod m

có x, y


Z thỏa mãn ax – my = 1.
Theo hệ quả 1.3, định lý hoàn toàn đƣợc chứng minh.
p

N đƣợc gọi là nguyên tố khi và chỉ khi p > 1 và a p với mọi a

Z, 1 < a
< p. Nói cách khác, p

N, p > 1, p là nguyên tố khi và chỉ khi với mọi a, b

Z, p|ab

p|a hoặc p|b
Định lý 1.5 (Định lý phần dƣ Trung Quốc)
Giả sử m
1
, …, m
r


N đôi một nguyên tố cùng nhau, gcd(m
i
, m
j
) = 1 với mọi
i

j. Có a

1
, …, a
r


Z. Khi đó, hệ phƣơng trình
x

a
i
(mod m
i
) (
ri 1
)
có một nghiệm duy nhất theo modulo M = m
1
x …xm
r
là
x =


r
i
iii
yMa
1
mod M
trong đó M

i
= M/m
i
và M
i
y
i


1 mod m
i

Chứng minh
Chú ý rằng M
i
là tích của tất cả các m
j
với j

i. Vì vậy, nếu j

i thì
M
i


0 mod m
j
. Chú ý, gcd(M
i

, m
i
) = 1, theo định lý 1.4, M
i
y
i


1 mod m
i

có một nghiệm y
i
. Do đó,
x =


r
i
iii
yMa
1

a
i
M
i
y
i



a
i
mod m
i

với mọi i,
ri 1
. Vì vậy, x là nghiệm của hệ phƣơng trình đồng dƣ.
Hàm Euler
ф: N

N đƣợc định nghĩa là
ф(m) = #{k

N |
mk 1
, gcd(k, m) = 1}

7
Định lý 1.6
ф(m) = #{a

Z
m
| ab

1 mod m với b

Z

m
}
Chứng minh Dựa vào định lý 1.1, ta có điều phải chứng minh.
Ví dụ:
Nếu p là một số nguyên tố, ф(p) = p – 1 và với a bất kỳ thuộc Z
p
, p a, tồn tại b

Z
p
để ab

1 mod p.
Giả sử p là số nguyên tố lẻ và x

Z,
11  px
, khi đó x đƣợc gọi là thặng dƣ
bậc 2 theo modul p nếu y
2


x mod p có một nghiệm y

Z
p
.
x đƣợc gọi là bậc 2 không có thặng dƣ nếu x không là thặng dƣ bậc 2 theo
modulo p và x


0 mod p.
Định lý 1.7 (Euler)
Với a, m

Z thỏa mãn gcd(a, m) = 1,
1
)(

 m
a
mod m
Chứng minh
Theo định lý 1.1 G
m
= {a

Z
m
| gcd(a, m) = 1} tạo thành nhóm nhân bậc ф(m).
Định lý 1.8 (Fermat)
Cho p là số nguyên tố và a

Z. Khi đó, ta có:
(1) a
p-1


1 mod p, nếu p a.
(2) a
p



a mod p
Chứng minh
(1) Vì ф(p) = p – 1 nên đây là trƣờng hợp đặc biệt của định lý Euler.
(2) Dễ dàng thấy nếu a

0 mod p là hiển nhiên, ngƣợc lại theo (1).
8
1.2. MỘT SỐ KHÁI NIỆM TRONG ĐẠI SỐ
1.2.1. Khái niệm Nhóm, Vành, Trường
1/. Nhóm
Nhóm là cấu trúc bao gồm tập G và toán tử hai ngôi * trên G. Với a, b

G, a * b

G đƣợc định nghĩa nhƣ sau:
1. a * (b * c) = (a * b) * c với mọi a, b, c

G
2. Tồn tại e

G thỏa mãn e * a = a * e = a với mọi a

G, (e đƣợc gọi là phần
tử trung hòa).
3. Với mỗi a

G, tồn tại một phần tử b


G thỏa mãn b * a = a * b = e
(b là duy nhất và đƣợc gọi là phần tử nghịch đảo của a)
Ký hiệu
,*G
là nhóm nhân và
,G
là nhóm cộng. Trong nhóm cộng, phần tử
trung hòa là 0 và phần tử nghịch đảo của a là –a. Trong nhóm nhân, phần tử trung hòa
là 1 và phần tử nghịch đảo của a là a
-1
.
,*G
đƣợc gọi là nhóm Abel nếu a * b = b * a với mọi a, b thuộc G.
Giả
,*G
là nhóm và H là tập con của G. Cấu trúc
,H
đƣợc gọi là nhóm con
của
,*G
nếu

là một thu hẹp của * tới H x H và
,H
là một nhóm.
Nếu
,*G
là nhóm hữu hạn thì số các phần tử của
,*G
đƣợc gọi là bậc của G

và ký hiệu là |G|. Nếu
,*G
là nhóm nhân hữu hạn, bậc của một phần tử a

G là
số nguyên dƣơng nhỏ nhất m thỏa mãn a
m
= 1. Trong nhóm nhân, với mọi phần tử
thuộc nhóm, m luôn tồn tại.
9
Định lý 1.9
,*G
là nhóm nhân hữu hạn bậc n. Nếu bậc của phần tử a

G là m thì
a
k


1 khi và chỉ khi m|k
Chứng minh
Nếu k = mq, thì a
k
= (a
m
)
q
=1. Ngƣợc lại, k = mq + r,
mr 0
. Khi đó

a
r
= a
k
. (a
-1
)
mq
= 1. Vì vậy, r phải bằng 0.
Hệ quả 1.10
Nếu
,*G
là nhóm nhân hữu hạn bậc n, thì:
(1) Với mọi a

G, a
n
= 1.
(2) Bậc của mọi phần tử a

G chia hết cho |G|.
Nếu a

G có bậc m thì H = {a
k
| k

Z }là nhóm con của G và có bậc m. Nếu
G có một phần tử a có bậc n = |G| thì G = {a
k

| k

Z} và G đƣợc gọi là một nhóm
cylic,
a đƣợc gọi là phần tử sinh của G. Ví dụ, tập hợp Z
n
= {0, 1, 2,…, n – 1} là một nhóm
cylic bậc n với toán tử cộng modulo n.
2/. Vành
Vành là tập R với 2 toán tử cộng (+) và nhân (.) với các điều kiện sau:
1.
,R
là nhóm Abel.
2. a . (b . c) = (a . b) . c với mọi a, b, c

R.
3. a . (b + c) = a . b + a . c và (a + b) . c = a . c + b . c với mọi a, b, c

R.
3/. Trường
Trƣờng F là vành với phần tử đơn vị e

0 và F* = {a

F | a

0 } là một nhóm nhân.
10
Định lý 1.11
Vành Z

p
là một trƣờng khi và chỉ khi p là số nguyên tố.
Chứng minh
Với a, b

Z, ta có: p là số nguyên tố

p|ab tức là p|a hoặc p|b
Nếu Z
p
là trƣờng thì
*
p
Z
tạo thành nhóm nhân. Nếu p a thì a

0 mod p.
Điều này nghĩa là a
*
p
Z
và tồn tại a
-1
. Do đó nếu p|ab và p a thì p|(ab)
-1
= b.
Vậy p là số nguyên tố.
Ngƣợc lại, giả sử p là số nguyên tố. Để chỉ ra rằng
*
p

Z
là nhóm nhân, ta
chỉ cần chỉ ra rằng với mọi
*
p
Zx
sẽ luôn tồn tại nghịch đảo x
-1
. Với a, b

Z
p
và
*
p
Zx
, nếu xa

xb mod p thì a

b mod p

a – b

0 mod p.
vì p|x(a – b)

p|x hoặc p|a – b và
*
p

Zx
tức là p x. Điều này suy ra
xZ
p
= {xa | a

Z
p
} = Z
p
trong đó xa = 1 với a

Z
p
vì luôn tồn tại phần tử 1 trong Z
p
.
Vậy mỗi
*
p
Zx
luôn có phần tử nghịch đảo.
Định nghĩa 1.1
Cho F là một trƣờng. Tập con K của F cũng là một trƣờng với các toán tử của
F, đƣợc gọi là trƣờng con của F, hay F là một trƣờng mở rộng của K. Nếu K

F thì K
đƣợc gọi là một trƣờng con hợp lệ của F. Trƣờng là tối giản nếu nó không có trƣờng
con hợp lệ nào. Với trƣờng F bất kỳ, giao F
0

của tất cả các trƣờng con hợp lệ là trƣờng
tối giản. Trƣờng F đƣợc gọi là có đặc số 0 nếu F
0


Q nghĩa là F chứa Q nhƣ một
trƣờng con. Trƣờng F đƣợc gọi là có đặc số p nếu F
0


Z
p
.
Trƣờng hữu hạn là trƣờng chứa hữu hạn các phần tử. Mọi trƣờng hữu hạn có
một số nguyên tố là đặc số của trƣờng. Một trƣờng F có đặc số thì với mọi a

F,
pa = 0
11
Định nghĩa 1.2
Trƣờng K với phần tử đơn vị nhân là 1.
(Các trƣờng hữu tỷ Q, số thực R, số phức C có đặc số là 0 )
Với p là nguyên tố thì GF(p
n
) có đặc số p.
Nếu H là trƣờng con của K thì H và K có cùng đặc số.
F là trƣờng mở rộng của trƣờng K. Ký hiệu F = K(

) nếu F là trƣờng mở rộng
nhỏ nhất của K chứa


. Nếu F là trƣờng hữu hạn đặc số p thì nhóm nhân F* = F \ {0}
là nhóm cylic và F = Z
p
(

) với

là phần tử sinh của nhóm F* và

đƣợc gọi là phần
tử nguyên thủy của F.
1.2.3. Không gian vector
K là trƣờng và V là nhóm cộng Abel. V đƣợc gọi là không gian vector
trên trƣờng K nếu một toán tử ánh xạ từ K x V

V đƣợc định nghĩa thỏa mãn các
điều kiện sau:
1. a(u + v) = au + av
2. (a + b)u = au + bu
3. a(bu) = (ab)u
4. 1u = u
Các phần tử của V đƣợc gọi là các vector và các phần tử của K đƣợc gọi là
các vô hƣớng. V là không gian vector trên trƣờng K và các v
1
, …, v
m


V. Vector trong

V có dạng c
1
v
1
+ c
2
v
2
+ …+ c
m
v
m
với c
i


K (i = 1, …, m) là tổ hợp tuyến tính của
v
1
, …, v
m
.
Tập hợp tất cả các tổ hợp tuyến tính gọi là span của v
1
, …, v
m
và ký hiệu là
span(v
1
, …, v

m
).
V là không gian vector trên trƣờng K. Các vector v
1
, …, v
m


V đƣợc gọi là
độc lập tuyến tính trên K, nếu không có các vô hƣớng c
1
,…, c
m


K thỏa mãn:
c
1
v
1
+ c
2
v
2
+ …+ c
m
v
m
= 0
12

Tập S = {u
1
, u
2
,…,u
n
} của các vector tạo thành cơ sở của V khi và chỉ khi
(u
1
, u
2
,…,u
n
) là độc lập tuyến tính và là span của V. Nếu S là một cơ sở của V thì mọi
phần tử của V đƣợc biểu diễn duy nhất dƣới dạng tổ hợp tuyến tính của các phần tử
của S. Nếu không gian vector V có cơ sở là một số hữu hạn các vector thì bất kỳ cơ sở
nào của V cũng sẽ có cùng số phần tử. Khi đó nó chính là chiều của V trên K.
Nếu F là trƣờng mở rộng của trƣờng K thì F là một không gian vector trên K.
Chiều của F trên K đƣợc gọi là bậc mở rộng của F trên K.
1.2.4. Vành tuyến tính
Cho F là một vành. Một đa thức bậc n trên F có dạng:



n
i
n
n
i
i

xaxaaxaxf
0
10
)(

với n là số nguyên dƣơng, các hệ số a
i


F (
ni 0
).
Cho 2 đa thức



n
i
i
i
xaxf
0
)(
và



n
i
i

i
xbxg
0
)(

ta định nghĩa tổng của f(x) và g(x) là



n
i
i
ii
xbaxgxf
0
)()()(

Cho 2 đa thức



n
i
i
i
xaxf
0
)(
và




m
j
j
j
xbxg
0
)(

ta định nghĩa tích của f(x) và g(x) là




nm
k
k
k
xcxgxf
0
)()(
với




mjni
kji
jik

bac
0,0

Vành đƣợc tạo thành bởi tất cả các đa thức trên F với toán tử thông thƣờng là cộng và
nhân đƣợc gọi là vành đa thức trên F và ký hiệu là F[x].
13
Định lý 1.12 (Thuật toán chia cho F[x])
Giả sử f(x) và g(x)

F[x] có bậc nguyên dƣơng, tồn tại duy nhất đa thức q(x),
r(x)

F[x] thỏa mãn
f(x) = g(x) . q(x) + r(x)
với bậc của r(x) nhỏ hơn bậc của g(x)
Nếu r(x) là đa thức 0 thì g(x) đƣợc gọi là ƣớc của f(x). Đa thức bất định f(x)
trong F[x] là tối giản nếu nó không có ƣớc có bậc thấp hơn f(x) trong F[x]. a

F là
nghiệm của f(x)

F[x] nếu f(a) = 0.
Hệ quả
Phần tử a

F là nghiệm của đa thức f(x)

F[x] khi và chỉ khi x – a là ƣớc của
f(x) trong F[x].
Chứng minh

Vì a là nghiệm nên f(a) = 0. Vì f(x) = (x –a).g(x) + r(x) nên bậc của r(x) nhỏ
hơn 1, tức là r(x) = c

F. Vì vậy, c = f(a) = 0. Ngƣợc lại, nếu f(x) = (x – a). q(x) thì
f(a) = 0.
Hệ quả 1.13
Một đa thức khác không f(x)

F[x] bậc n có nhiều nhất n nghiệm trong F.
1.2.5. Trường hữu hạn
Trƣờng hữu hạn là trƣờng có hữu hạn các phần tử ký hiệu là F
q
hoặc GF(q) với
q là số các phần tử.
14
Định lý 1.14
F là trƣờng mở rộng bậc n trên trƣờng hữu hạn K. Nếu K có q phần tử thì F có
q
n
phần tử.
Chứng minh
Giả sử {
n

, ,
1
}là cơ sở của F nhƣ là một không gian vector trên K. Mọi
F

sẽ có dạng

nn
cc


11
trong đó
Kc
i

(i = 1,…, n). Vì mỗi c
i
có thể là
một trong q phần tử của K nên số các tổ hợp tuyến tính là q
n
.
Định lý
Nếu F là trƣờng hữu hạn có đặc số p thì F có p
n
phần tử với n nguyên dƣơng.
Vì vậy, mọi trƣờng hữu hạn là một mở rộng của trƣờng đẳng cấu Z
p
với p là
đặc số của F.
Định lý 1.15
Trƣờng hữu hạn F =
n
p
F
là một trƣờng mở rộng của Z
p

bậc n và mọi phần tử
của
n
p
F
là một nghiệm của đa thức
xx
n
p

trên Z
p
.
Chứng minh
Đặc số của
n
p
F
là p. Tập hợp F* = F \ {0} tạo thành nhóm nhân bậc p
n
-1. Với
*F

, bậc của trong nhóm chia hết cho bậc của F*, p
n
– 1. Vì vậy, với mọi
*F

,
chúng ta có

1
1


n
p

hay


n
p
. Vì
xx
n
p

có nhiều nhất p
n
nghiệm,
n
p
F
gồm tất cả
các nghiệm của
xx
n
p

trên Z

p
.
Ví dụ
Trƣờng
r
F
2
chứa F
2
(hoặc Z
2
). Nếu viết toán tử cộng trong
r
F
2
nhƣ là phép cộng
vector và viết phép nhân k và v (k, v

r
F
2
) là một tích vô hƣớng của k

F
2
và v
r
F
2


.
Khi đó
r
F
2
đƣợc xem là không gian vector trên F
2
với chiều r. Ký hiệu d là chiều của
không gian vector này. Có thể thực hiện ánh xạ 1 – 1 giữa các phần tử trong không
gian vector d chiều và các d-tuple của các phần tử trong F
2
. Vì vậy, có 2
d
phần tử trong
không gian vector này. Vì d = r,
r
F
2
là không gian vector r chiều.
15

m
q
F
là một mở rộng của F
q
. 2 phần tử
m
q
F


,
là liên hợp trên F
q
nếu

và


là các nghiệm của cùng một đa thức tối giản bậc m trên F
q
.
12
, ,,,
m
qqq

là các
liên hợp của
m
q
F

với F
q
.

m
q
F

là một mở rộng của F
q
. Một cơ sở của
m
q
F
(không gian vector trên F
q
) của
{
12
, ,,,
m
qqq

} gồm
m
q
F

và các liên hợp của nó với F
q
, đƣợc gọi là cơ sở
trực giao của
m
q
F
trên F
q
. Mọi trƣờng mở rộng bậc hữu hạn của một trƣờng hữu hạn có

một cơ sở trực giao.
16
1.3. KHÁI NIỆM VỀ ĐỘ PHỨC TẠP CỦA THUẬT TOÁN
1.3.1. Khái niệm thuật toán

Thuật toán là một dãy hữu hạn các thao tác được bố trí theo một trình tự xác
định nhằm giải quyết một bài toán
- Thao tác, hay còn gọi là tác vụ, phép toán (Operation) hay lệnh (Command),
chỉ thị (Instruction) là một hành động cần đƣợc thực hiện bởi cơ chế thực hiện thuật
toán.
Mỗi thao tác biến đổi bài toán từ một trạng thái trƣớc (hay trạng thái nhập)
sang trạng thái sau (hay trạng thái xuất).Thực tế mỗi thao tác thƣờng sử dụng một số
đối tƣợng trong trạng thái nhập (các đối tƣợng nhập )và sản sinh ra các đối tƣợng mới
trong trạng thái xuất (các đối tƣợng xuất). Quan hệ giữa 2 trạng thái xuất và nhập cho
thấy tác động của thao tác. Dãy các thao tác của thuật toán nối tiếp nhau nhằm biến
đổi bài toán từ trạng thái ban đầu đến trạng thái kết quả.
Mỗi thao tác có thể phân tích thành các thao tác đơn giản hơn.
- Trình tự thực hiện các thao tác phải đƣợc xác định rõ ràng trong thuật toán.
Cùng một tập hợp thao tác nhƣng xếp đặt theo trình tự khác nhau sẽ cho kết quả khác
nhau.
1.3.2. Độ phức tạp của thuật toán

Lý thuyết thuật toán và các hàm số tính đƣợc ra đời từ những năm 30 của thế kỷ
20 đã đặt nền móng cho việc nghiên cứu các vấn đề “tính đƣợc”, “giải đƣợc” trong
toán học, đƣa đến nhiều kết quả rất quan trọng và lý thú. Nhƣng từ cái “tính đƣợc” một
cách trừu tƣợng, hiểu theo nghĩa tiềm năng, đến việc tính đƣợc trong thực tế của khoa
học tính toán bằng máy tính điện tử, là cả một khoảng cách rất lớn. Vấn đề là do ở chỗ
những đòi hỏi về không gian vật chất và về thời gian để thực hiện các tiến trình tính
toán nhiều khi vƣợt quá xa những khả năng thực tế. Từ đó, vào khoảng giữa những
năm 60 (của thế kỷ trƣớc), một lý thuyết về độ phức tạp tính toán bắt đầu đƣợc hình

thành và phát triển nhanh chóng, cung cấp cho chúng ta nhiều hiểu biết sâu sắc về bản
chất phức tạp của các thuật toán và các bài toán, cả những bài toán thuần túy lý thuyết
17
đến những bài toán thƣờng gặp trong thực tế. Sau đây giới thiệu sơ lƣợc một số khái
niệm cơ bản và vài kết quả sẽ đƣợc dùng đến của lý thuyết đó.
Trƣớc hết, hiểu độ phức tạp tính toán (về không gian hay về thời gian) của một
tiến trình tính toán là số ô nhớ đƣợc dùng hay số các phép toán sơ cấp đƣợc thực hiện
trong tiến trình tính toán đó.
Dữ liệu đầu vào đối với một thuật toán thƣờng đƣợc biểu diễn qua các từ trong
một bảng ký tự nào đó. Độ dài của một từ là số ký tự trong từ đó.
Cho một thuật toán A trên bảng ký tự  (tức có đầu vào là các từ trong ). Độ
phức tạp tính toán của thuật toán A đƣợc hiểu là một hàm số f
A
(n) sao cho với mỗi số
n, f
A
(n) là số ô nhớ, hay số phép toán sơ cấp tối đa mà A cần để thực hiện tiến trình
tính toán của mình trên các dữ liệu vào có độ dài  n. Ta nói thuật toán A có độ phức
tạp thời gian đa thức, nếu có một đa thức P(n) sao cho với mọi n đủ lớn ta có f
A
(n) 
P(n), trong đó f
A
(n) là độ phức tạp tính toán theo thời gian của A.
Về sau khi nói đến các bài toán, ta hiểu đó là các bài toán quyết định, mỗi bài
toán Q nhƣ vậy đƣợc xác định bởi:
- Một tập các dữ liệu vào I (trong một bảng ký tự  nào đó),
- Một câu hỏi q trên các dữ liệu vào, sao cho với mỗi dữ liệu vào x

1, câu hỏi q

có một trả lời đúng hoặc sai.
Bài toán quyết định Q là giải được, nếu có thuật toán để giải nó, tức là thuật
toán làm việc có kết thúc trên mọi dữ liệu vào các bài toán, và cho kết quả đúng hoặc
sai tùy theo câu hỏi q trên dữ liệu đó có trả lời đúng hoặc sai. Bài toán Q là giải được
trong thời gian đa thức, nếu có thuật toán giải nó với độ phức tạp thời gian đa thức.
Thuật toán lại chia làm 2 loại: đơn định( tất định) và đa định( không tất định).
Sau đây là vài ví dụ về các bài toán quyết định:
Bài toán SATISFIABILYTY (viết tắt là SAT):
- Mỗi dữ liệu vào là một công thức F của logic mệnh đề, đƣợc viết dƣới dạng
hội chuẩn tắc, tức dạng hội của một số các “clause”.
- Câu hỏi là: công thức F có thỏa đƣợc hay không?
18
Bài toán CLIQUE:
- Mỗi dữ liệu vào là một graph G và một số nguyên k.
- Mỗi câu hỏi là: Graph G có một clique với ≥ k đỉnh hay không? (một clique
của G là một graph con đầy đủ của G).
Bài toán KNAPSACK:
- Mỗi dữ liệu là một bộ n + 1 số nguyên dƣơng I = (s
1
, s
n
; T).
- Câu hỏi là: có hay không một vectơ Boole (x
1
, ,x
n
) sao cho




n
i
Tsixi
1
?

(vectơ Boole là vectơ có các thành phần là 0 hoặc 1)
Bài toán thặng dƣ bậc hai:
- Mỗi dữ liệu gồm hai số nguyên dƣơng (a, n).
- Câu hỏi là: a có là thặng dƣ bậc hai theo mod n hay không?
Bài toán hợp số:
- Mỗi dữ liệu là một số nguyên dƣơng N.
- Câu hỏi: N là hợp số không? Tức có hay không hai số m, n >1 sao cho N =
m.n?
Tƣơng tự, nếu đặt câu hỏi là “N là số nguyên tố hay không?” thì ta đƣợc bài
toán số nguyên tố.
Đối với tất cả các bài toán kể trên, trừ bài toán hợp số và số nguyên tố, cho đến
nay ngƣời ta đều chƣa tìm đƣợc thuật toán giải chúng trong thời gian đa thức.
1.3.3 Một số lớp bài toán

Xét một vài lớp các bài toán đƣợc xác định theo độ phức tạp tính toán của
chúng. Trƣớc hết, định nghĩa P là lớp tất cả các bài toán có thể giải đƣợc bởi thuật toán
trong thời gian đa thức.
19
Giả sử cho hai bài toán A và B với các tập dữ liệu trong hai bảng ký tự tƣơng
ứng là

1
và


2
. Một thuật toán f:

*
1
→

*
2
đƣợc gọi là một phép quy
dẫn bài toán A về bài toán B, nếu nó biến mỗi dữ liệu x của bài toán A thành một dữ
liệu f(x) của bài toán B, và sao cho câu hỏi của A trên x có trả lời đúng khi và chỉ khi
câu hỏi của B trên f(x) cũng có trả lời đúng. Ta nói bài toán A quy dẫn được về bài
toán B

trong thời gian đa thức, và ký hiệu A

B, nếu có thuật toán f với độ phức tạp
thời gian đa thức qui dẫn bài toán A về bài toán B. Dễ thấy rằng, nếu A

B và B

P,
thì cũng có A

P.
Một lớp quan trọng các bài toán đã đƣợc nghiên cứu nhiều là lớp các bài toán
khá thƣờng gặp trong thực tế nhƣng cho đến nay chƣa có khả năng nào chứng tỏ là
chúng có thể giải đƣợc trong thời gian đa thức. Đó là lớp các bài toán NP đƣợc định
nghĩa sau đây:

Cùng với khái niệm thuật toán tất định thông thƣờng (có thể mô tả chính xác
chẳng hạn bởi máy Turing tất định), xét khái niệm thuật toán không đơn định với một
ít thay đổi nhƣ sau: nếu đối với máy Turing tất định, khi máy đang ở một trạng thái q
và đang đọc một ký tự a thì cặp (q, a) xác định duy nhất một hành động kế tiếp của
máy, còn đối với máy Turing không đơn định, qui ƣớc rằng (q, a) xác định không phải
duy nhất mà là một tập hữu hạn các hành động kế tiếp; máy có thể thực hiện trong
bƣớc kế tiếp một trong các hành động đó. Nhƣ vậy, đối với một dữ liệu vào x, một
thuật toán không đơn định đƣợc (đƣợc xác định chẳng hạn bởi một máy Turing không
đơn định) không phải chỉ có một tiến trình tính toán duy nhất, mà có thể có một số hữu
hạn những tiến trình tính toán khác nhau.
Ta nói thuật toán không đơn định T chấp nhận dữ liệu x, nếu với dữ liệu vào
chấp nhận (tức với kết quả đúng). Một bài toán A đƣợc gọi là giải được bởi thuật toán
không đơn định trong thời gian đa thức nếu có một thuật toán không đơn định T và
một đa thức p(n) sao cho với mọi dữ liệu vào x có độ dài n khi và chỉ khi thuật toán T
chấp nhận x bởi một tiến trình tính toán có độ phức tạp thời gian  p(n). Ta ký hiệu lớp
tất cả với các bài toán giải đƣợc bởi thuật toán không đơn định trong thời gian đa thức
là NP.
20
Ngƣời ta đã chứng tỏ đƣợc rằng tất cả những bài toán trong các ví dụ kể trên và
rất nhiều các bài toán tổ hợp thƣờng gặp khác đều thuộc lớp NP, dù rằng hầu hết
chúng đều chƣa đƣợc chứng tỏ là thuộc P. Một bài toán A đƣợc gọi là NP-đầy đủ, nếu
A

NP và với mọi B

NP đều có B

A.
Lớp NP có một số tính chất sau đây:
1) P


NP
2) Nếu P
1

P
2
và P
2


NP, thì P
1

NP


3) Nếu P
1
, P
2

NP, P
1

P
2,
và P
1
là NP- đầy đủ, thì P

2
cũng là NP-đầy đủ
4) Nếu có A sao cho A là NP-đầy đủ và A

P, thì P=NP

Từ các tính chất đó có thể xem rằng trong lớp NP, P là lớp con các bài toán
“dễ” nhất, còn các bài toán NP đầy đủ là các bài toán “khó” nhất; nếu có ít nhất một
bài toán NP đầy đủ đƣợc chứng minh là thuộc P, thì lập tức suy ra P = NP, dù rằng
cho đến nay tuy đã có rất nhiều cố gắng nhƣng toán học vẫn chƣa tìm đƣợc con đƣợc
nào hy vọng đi đến giải quyết vấn đề