ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TRẦN ĐỨC DŨNG XÂY DỰNG CƠ SỞ DỮ LIỆU
CÁC ĐA THỨC BẤT KHẢ QUY

LUẬN VĂN THẠC SĨ
NGÀNH HỆ THỐNG THÔNG TIN
Thành phố Hồ Chí Minh - 2011
LỜI CẢM ƠN
\ [

Trước hết tôi xin bày tỏ lòng biết ơn chân thành đối với thầy hướng dẫn khoa học, PGS.
TS. Nguyễn Đình Thúc, người đã gợi ý cho tôi một đề tài hết sức thú vị, đồng thời đã hết
lòng giúp đỡ tôi trong suốt quá trình thực hiện đề tài với một sự quan tâm sâu sắc và bền
bỉ. Chính sự giúp đỡ quý báu và sự quan tâm sâu sắc của thầy đã là nguồn động viên vô
hạ
n và là chỗ dựa tinh thần vững chắc giúp tôi có thể thực hiện đề tài một cách nhanh
chóng và thuận lợi.
Tôi xin bày tỏ lòng biết ơn đối với quý thầy cô khoa Công nghệ Thông tin, Đại học Khoa
học Tự nhiên đã truyền đạt cho tôi những kiến thức khoa học vô cùng quý báu làm nền
tảng cho việc thực hiện đề tài và quá trình nghiên cứu khoa học sau này. Đặc biệt là PGS.
TS. Đinh Điền, Đại học Khoa học Tự nhiên và thầ
y Trần Đình Long (nghiên cứu sinh
tiến sĩ), Đại học Huế, những người cũng đã giúp đỡ tôi rất nhiều trong quá trình thực hiện
đề tài.
Cuối cùng tôi xin bày tỏ lòng biết ơn đối với gia đình, đồng nghiệp và bạn bè đã hết lòng
ủng hộ và động viên tôi trong suốt quá trình học tập và thực hiện đề tài. Tôi xin cảm ơn
tất cả các bạn lớp Hệ thống Thông tin Khóa 17 đã cho tôi nhữ
ng tháng ngày tốt đẹp nhất
dưới mái trường thân yêu của chúng ta.
1

MỤC LỤC
DANH MỤC HÌNH 4
DANH MỤC BẢNG 5

2.3.3.2 Phương pháp Primitive-Based 51
2.3.3.3 Phương pháp Varshamov 52
2.3.3.4 Phương pháp Kyuregyan 54
3.2.3.5 So sánh giữa các phương pháp tổng hợp 57
2.3.3.6 Giải thuật kiểm tra tính nguyên thủy 58
2.3.4 Cấu trúc lưu trữ cho cơ sở dữ liệu các đa thức bất khả quy 60
2.3.4.1 Biểu diễn đa thức 60
2.3.4.2 Hàm băm và cấu trúc bảng 60
3

2.3.4.3 Các giải thuật tìm kiếm và thao tác trên cơ sở dữ liệu 62
CHƯƠNG 3 CÀI ĐẶT THỬ NGHIỆM 64
3.1 Môi trường phát triển ứng dụng 64
3.2 Phát sinh cơ sở dữ liệu ban đầu 64
3.3 Tổng hợp các đa thức bất khả quy bậc cao 69
3.4 Phát sinh các đa thức bất khả quy bậc cao dạng đặc biệt 72
3.5 Thao tác trên cơ sở dữ liệu 74
3.6 Phân tích đa thức bất kỳ thành các nhân tử bất khả quy 76
3.7 Sử dụng giao diện Web 78
3.8 Mở rộng một số chức năng trên trường hữu hạn 

bất kỳ 82
3.9 Đánh giá hệ thống và so sánh kết quả 87
CHƯƠNG 4 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 90
4.1 Các kết quả đã đạt được 90
4.2 Một số hạn chế 90
4.3 Hướng phát triển 91
TÀI LIỆU THAM KHẢO 92

4

Bảng 1.1 – So sánh các phương pháp phân tích đa thức thành nhân tử bất khả quy 13
Bảng 1.2 – Sự phân bố của các đa thức bất khả quy trên trường 

16
Bảng 1.3 – Bảng phép toán cộng trên trường mở rộng 

24
Bảng 1.4 – Bảng phép toán nhân trên trường mở rộng 

24
Bảng 2.1 – Cấu trúc lưu trữ cho đa thức bất khả quy 61
Bảng 3.1 – So sánh hiệu quả của các giải thuật phát sinh đa thức bất khả quy 68
Bảng 3.2 – Cấu trúc lưu trữ cho đa thức bất khả quy trên trường hữu hạn 

bất kỳ 83
Bảng 3.3 – So sánh số lượng các đa thức bất khả quy bậc  giữa 

và 

87
Bảng 3.4 – Kết quả đánh giá sơ bộ về hệ thống cài đặt thử nghiệm 89






6

CHƯƠNG MỞ ĐẦU

7

và thuận tiện, giảm thiểu chi phí phát sinh các đa thức bất khả quy và góp phần nâng
cao hiệu năng của toàn bộ hệ thống.
0.3. Mục đích và nội dung nghiên cứu
Đa thức bất khả quy có nhiều ứng dụng thực tiễn trong khi việc phát sinh ra các đa thức
bất khả quy lại thường kém hiệu quả và hao tốn chi phí. Mục đích nghiên cứu của đề
tài là tìm kiếm một giải pháp tối
ưu nhằm phát sinh sẵn ra các đa thức bất khả quy phục
vụ tốt nhất cho các yêu cầu của ứng dụng. Nội dung nghiên cứu của đề tài là tìm kiếm
các giải thuật phát sinh và tổng hợp các đa thức bất khả quy và một giải pháp lưu trữ và
tìm kiếm hiệu quả sao cho có thể trả về các đa thức bất khả quy một cách nhanh chóng
và tiện lợi nhất cho các ứng dụng thực tiễn.
Để đề tài có tính khả thi trong điều kiện nguồn lực bị hạn chế, luận văn sẽ chỉ tập trung
nghiên cứu các đa thức bất khả quy chủ yếu trên trường nhị phân 

là trường được sử
dụng phổ biến nhất trong tin học. Tuy nhiên, các kết quả nghiên cứu có thể dễ dàng mở
rộng sang một trường hữu hạn 

bất kỳ một cách trực tiếp, hoặc chỉ với một số thay
đổi nhỏ. Trong đề tài này chúng tôi cũng sẽ trình bày với tính cách minh họa và cài đặt
thử nghiệm một số chức năng tương tự của các đa thức bất khả quy trên một trường
hữu hạn 

bất kỳ.
0.4. Đóng góp của luận văn
Về mặt phương pháp luận đề tài đã đề xuất một phương pháp phát sinh ra các đa thức
bất khả quy một cách có hệ thống. Phương pháp này kết hợp nhiều phương thức phát
sinh ra các đa thức bất khả quy vào một phương thức thống nhất, đó là lưu trữ và tìm

dụ minh họa về ứng dụng của các đa thức bất khả quy trong thực tiễn.
Chương 2: Xây dựng cơ sở dữ liệu các đa thức bất khả quy
Chương này trình bày một số khái niệm và định lý toán học cơ sở, các phương pháp và
giải thuật cơ bản được sử dụng trong quá trình thực hiện việc xây dựng kho c
ơ sở dữ
liệu các đa thức bất khả quy.
9

Chương 3: Cài đặt thử nghiệm
Chương này trình bày một số kết quả và số liệu thu thập được trong quá trình cài đặt
thử nghiệm và vận hành hệ thống, đánh giá hệ thống và so sánh kết quả.
Chương 4: Kết luận và hướng phát triển
Chương này trình bày những thành quả đạt được, những điểm còn hạn chế, khả năng
ứng dụng và hướng phát triển của hệ thống trong t
ương lai.

10

CHƯƠNG 1
GIỚI THIỆU TỔNG QUAN
1.1. Vai trò của các đa thức bất khả quy
Các đa thức bất khả quy trên một trường hữu hạn 

đóng vai trò tương tự như các số
nguyên tố trong vành số nguyên: chúng là các đơn vị cấu trúc cơ bản và do đó nhiều
tính chất đặc trưng của toàn bộ cấu trúc có thể được suy ra từ tính chất của các phần tử
cơ bản này.
Mỗi số nguyên bất kỳ trong vành số nguyên đều có thể phân tích một cách duy nhất
thành tích của các thừa số nguyên tố. Tương tự, mỗi đa thức bấ
t kỳ trên một trường

a thức (đa thức tích) thành nhân tử là các đa thức bất
khả quy. Hoặc quá trình xây dựng các đa thức bất khả quy có thể quy về quá trình phân
tích thành nhân tử bất khả quy của một đa thức khác [10]. Các đặc điểm này rất dễ
nhận ra trong các giải thuật đã được đề xuất.
Đối với bài toán phân tích đa thức thành các nhân tử bất khả quy có hai nhóm giải thuật
được sử dụng: nhóm các giải thuậ
t tất định (deterministic) và nhóm các giải thuật ngẫu
nhiên hay không tất định (randomized hay non-deterministic). Hầu hết các giải thuật
đều có độ phức tạp thời gian đa thức theo các biến số  (bậc của đa thức) và  (kích
thước hay số phần tử của trường hữu hạn). Thông thường khi giải bài toán phân tích
một đa thức thành các nhân tử bất khả quy ta phải giải một bài toán phụ
nào đó, chẳng
hạn như bài toán tìm nghiệm của một đa thức, tìm một phần tử 

sao cho 




( gọi là 

non-residue), hoặc các bài toán có liên quan đến đại số tuyến
tính, chẳng hạn như tìm hạng của một ma trận hay tìm cơ sở của không gian con null
space của một không gian tuyến tính như trong giải thuật Berlekamp mà chúng ta sẽ
cài đặt sau này (ở chương 2).
12

Ta quy ước nếu thời gian thực thi được xác định bởi hàm , thì điều đó có nghĩa
là giải thuật tương ứng cần thực hiện 


13

Bảng 1.1. So sánh các phương pháp phân tích đa thức thành nhân tử bất khả quy
Tác giả Thời gian thực thi và điều kiện áp dụng
Tonelli
(1891)
log
Chỉ phân tích các đa thức bậc 2 trên trường nguyên tố


. Cần tìm phần tử 

không phải là lũy thừa bậc 2
của bất kỳ phần tử 

nào (



).
Arwin
(1918)



log

log









1, thay vì
phân tích hoàn toàn 





1



1






1








log

log


Dựa theo phương pháp ngẫu nhiên của Collins và Knuth
(1967) và của Zassenhaus (1969). Xác suất thành công
chưa được phân tích đầy đủ. Sử dụng công cụ giải hệ
phương trình tuyến tính thưa (sparse linear system
solver, Wiedemann 1986), thời gian thực thi của phương
pháp này có thể giảm xuống còn log

log


hoặc 

loglog

, đồng thời giảm không
gian lưu trữ xuống còn 



(thay vì 

) nếu áp
dụng cải tiến của Cantor và Zassenhaus (1981).



loglog


Giải thuật ngẫu nhiên. Phương pháp phân tích thành
nhân tử bất khả quy đầu tiên có thời gian thực thi đa
thức với không gian lưu trữ .

15

Schoof
(1985)

log


loglog


Chỉ phân tích các đa thức bậc 2 trên trường nguyên tố


. Cần tính các căn bậc 2 [] của các hằng số
nguyên, chẳng hạn như -1. Độ phức tạp thời gian được
tính theo thao tác trên bit. Đây là giải thuật phân tích tất
định duy nhất được biết đến mà không yêu cầu thời gian
thực thi đa thức theo đối số log.
Huang
(1991a, 1991b)





1


/
||
1.3.1,
trong đó  là hàm Moebius (xem chương 2, trang 27, công thức 2.2.1.2). Số liệu
thống kê của các đa thức có bậc nhỏ hơn hay bằng 30 trên trường nhị phân 

được cho
trong bảng 1.2 dưới đây.
Bảng 1.2. Sự phân bố của các đa thức bất khả quy trên trường 


Bậc 
Tổng số các
ĐTBKQ bậc 
Tổng số các
đa thức bậc 
Tổng số các
ĐTBKQ bậc nhỏ
hơn hay bằng 
Tổng số các đa thức
bậc nhỏ hơn hay
bằng 
1

18
128
41
254
8
30
256
71
510
17

9
56
512
127
1022
10
99
1024
226
2046
11
186
2048
412
4094
12
335
4096
747

19
27594
524288
58636
1048574
20
52377
1048576
111013
2097150
21
99858
2097152
210871
4194302
22
190557
4194304
401428
8388606
23
364722
8388608
766150
16777214
24
698870
16777216
1465020
33554430


• Cột 1 là bậc của các đa thức khảo sát.
• Cột 2 là số các đa thức bất khả quy có bậc , cột 3 là số các đa thức có bậc .
18

• Cột 4 là số các đa thức bất khả quy có bậc nhỏ hơn hay bằng . Cột 5 là số các
đa thức có bậc nhỏ hơn hay bằng .
Chẳng hạn, với 4 ta có 16 đa thức bậc 4, trong số đó có 3 đa thức bất khả quy (bậc
4). Tương tự ta có 30 đa thức có bậc nhỏ hơn hay bằng 4, trong số đó có 8
đa thức bất
khả quy có bậc nhỏ hơn hay bằng 4.
Các con số này tăng lên rất nhanh. Chẳng hạn với 10 ta có 1024 đa thức bậc 10,
trong số đó có 99 đa thức bất khả quy; có 2046 đa thức có bậc nhỏ hơn hay bằng 10,
trong số đó có 226 đa thức bất khả quy có bậc nhỏ hơn hay bằng 10.
Với giá trị của 30, ta đ
ã có 1.073.741.824 (hơn 1 tỷ!) đa thức bậc 30, trong số đó
có 35.790.267 (hơn 35 triệu!) đa thức bất khả quy; có 2.147.483.646 (hơn 2 tỷ) đa thức
có bậc nhỏ hơn hay bằng 30, trong số đó có 74.248.451 (hơn 74 triệu) đa thức bất khả
quy có bậc nhỏ hơn hay bằng 30.
Nếu ta xây dựng một cơ sở dữ liệu bao gồm tất cả các đa thức bất kh
ả quy có bậc nhỏ
hơn hay bằng 30 trên trường 

thì ta đã có hơn 74 triệu đa thức bất khả quy (trên
trường 

con số này còn lớn hơn nhiều).
Sự phân bố của các đa thức bất khả quy có bậc 10 trên trường 

được biểu diễn

1000
1500
2000
2500
12345678910
ĐathứcBKQbậcn
Đathứcbậcn
ĐathứcBKQbậc≤n
Đathứcbậc≤n
20

Mọi phần tử  của nhóm đều có tính chất là 
||
1. Nếu hai số nguyên  và  thỏa
1 ( nguyên) thì sau hai lần nâng lên lũy thừa của thông điệp  ta có
kết quả 







.1, tức là trở về nguyên vẹn thông
điệp ban đầu.
Độ an toàn của hệ thống phụ thuộc vào độ khó của quá trình phân tích số  thành tích
của hai số nguyên tố  và .
Quy trình trên được mô tả bởi giải thuật dưới đây.
Giải thuật RSA cổ điển
Về phía người gửi ():

(7) Giải mã bằng cách tính 

 (

) rồi tính 



 ().
21

Kết quả trên đã được mở rộng một cách rất tự nhiên sang vành đa thức. Giải thuật RSA
dựa vào đa thức bất khả quy dưới đây là tương ứng (counterpart) của giải thuật RSA cổ
điển đã nêu trên.
Giải thuật RSA dựa vào các đa thức bất khả quy
Quá trình tạo khóa (của người gửi )
(1) Chọn số nguyên t
ố lẻ  và hai đa thức bất khả quy  và  trên
trường 

.
(2) Tính 







.




 ( được xác định ở đây là duy nhất).
(6) Công bố khóa công khai ,



, và giữ  là khóa bí mật.
Quá trình ký (của người gử
i )
(7) Nhận thông điệp  trong hệ thặng dư đầy đủ modulo  của 

.
(8) Tính 








 là một đa thức trong hệ thặng dư đầy đủ modulo
 của 

.
(9) Sử dụng khóa bí mật  để tính 





 (

).
(3)  phục hồi  bằng cách tính 






.
Ví dụ với các bộ số cụ thể:
389, 





37643, 





384

310 trên 





13

, 












1
3

, 







13






13
















13


13


Để đơn giản, trong ví dụ trên ta sử dụng hàm mã hóa  là hàm đồng nhất (
