Tóm tắt Luận án Nghiên cứu phương pháp sàng trường số ứng dụng trong phân tích mã

1 
BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG 
VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ 
----------------------- 
ĐINH QUỐC TIẾN 
NGHIÊN CỨU PHƯƠNG PHÁP SÀNG TRƯỜNG SỐ 
ỨNG DỤNG TRONG PHÂN TÍCH MÃ 
Chuyên ngành: Cơ sở toán học cho tin học 
Mã số: 62 46 01 10 
TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC 
HÀ NỘI – 2014 
2 
Công trình được hoàn thành tại: 
VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ 
BỘ QUỐC PHÒNG 
Người hướng dẫn khoa học: 
1. TS. Lều Đức Tân 
2. TS. Phạm Việt Trung 
Phản biện 1: PGS.TS Hoàng Văn Tảo 
 Ban Cơ yếu Chính Phủ. 
Phản biện 2: PGS.TS Nguyễn Duy Bảo 
 Học viện Kỹ thuật Quân sự. 
Phản biện 3: TS Thái Danh Hậu 
 Viện Khoa học và Công nghệ quân sự. 
Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp 
Viện họp tại Viện Khoa học và Công nghệ quân sự vào hồi 
.. ngày .. tháng .. năm 2014. 
Có thể tìm hiểu luận án tại thư viện: 
- Thư viện Viện Khoa học và Công nghệ quân sự 
- Thư viện Quốc gia Việt nam 
1 
MỞ ĐẦU 
1. Tình hình nghiên cứu trong và ngoài nước 
Mật mã khóa công khai là một phần quan trọng trong các mạng 
truyền thông hiện đại. Hệ mật khóa công khai RSA có độ an toàn dựa 
vào tính khó giải của bài toán phân tích số trong trường hợp số modulo N 
chỉ có hai ước nguyên tố lớn xấp xỉ nhau. Với các hợp số N lớn hơn 120 
chữ số thập phân thì sàng trường số là lựa chọn tối ưu, vì nó là phương 
pháp phân tích số nguyên lớn nhanh nhất hiện nay. 
Tại Việt Nam, hệ mật khóa công khai RSA được ứng dụng khá 
rộng rãi cả trong lĩnh vực kinh tế xã hội và an ninh quốc phòng. Trong 
Ban Cơ yếu Chính phủ cũng đã có nhiều đề tài nghiên cứu về vấn đề 
này, tuy nhiên vẫn chưa có những nghiên cứu sâu nhằm cải tiến phương 
pháp sàng trường số ứng dụng phân tích đánh giá hệ mật RSA. 
2. Tính cấp thiết 
 Hiện nay ngành Cơ yếu Việt Nam đang rất cần những nghiên 
cứu về vấn cải tiến phương pháp sàng trường số nhằm: 
 Phân tích đánh giá các hệ mật dựa vào bài toán phân tích số và 
tính logarit rời rạc. 
 Góp phần vào việc nghiên cứu xây dựng tiêu chuẩn cho hệ mật 
khóa công khai RSA. 
Xuất phát từ thực tế đó, NCS chọn đề tài “Nghiên cứu phương 
pháp sàng trường số ứng dụng trong phân tích mã”. 
3. Đối tượng và phạm vi nghiên cứu 
 Đối tượng nghiên cứu của Luận án: 
- Hệ mật khóa công khai RSA và độ an toàn của nó. 
- Phương pháp sàng trường số phân tích số nguyên lớn. 
2 
- Chọn đa thức sàng cho phương pháp sàng trường số. 
- Cải tiến các thuật toán sàng cho phương pháp sàng trường 
số. 
 Phạm vi nghiên cứu của Luận án: 
- Nghiên cứu cơ sở lý thuyết và xây dựng các thuật toán chọn 
đa thức sàng cho phương pháp sàng trường số. 
- Nghiên cứu và cải tiến các thuật toán sàng áp dụng cho 
phương pháp sàng trường số. 
4. Mục tiêu nghiên cứu 
 Nghiên cứu cở lý thuyết và xây dựng các thuật toán chọn cặp đa 
thức sàng cho phương pháp sàng trường số. 
 Nghiên cứu cải tiến và đánh giá hiệu quả của các thuật toán sàng 
áp dụng cho phương pháp sàng trường số. 
5. Phương pháp nghiên cứu 
 Dựa trên cơ sở lý thuyết của phương pháp sàng trường số. 
 Dựa trên cơ sở lý thuyết của các thuật toán chọn đa thức sàng và 
các thuật toán sàng. 
 Dựa trên phương pháp tích hợp, công nghệ lập trình song song. 
6. Ý nghĩa khoa học và thực tiễn 
 Ý nghĩa khoa học: Góp phần vào việc phân tích đánh giá và xây 
dựng tiêu chuẩn cho hệ mật khóa công khai RSA. 
 Ý nghĩa thực tiễn: Đáp ứng nhu cầu đảm bảo an toàn mật mã 
trong các lĩnh vực kinh tế xã hội và an ninh quốc phòng. 
7. Bố cục của luận án 
Luận án gồm 03 chương cùng với các phần mở đầu, kết luận, 
danh mục các công trình, bài báo khoa học đã được công bố của tác giả 
và 02 phần phụ lục. 
3 
CHƯƠNG 1 
TỔNG QUAN VỀ HỆ MẬT RSA VÀ BÀI TOÁN PHÂN TÍCH SỐ 
1.1. Hệ mật mã khóa công khai RSA 
1.1.1. Thiết lập tham số khóa RSA 
Hệ mật khoá công khai RSA sử dụng cặp khoá công khai (N, e), 
bí mật (N, d), chúng được sinh trước theo thuật toán sinh khoá RSA. 
1.1.2. Hệ mật khóa công khai RSA 
Khoá công khai (N, e) được sử dụng làm khoá mã (Thuật toán 
1), và khoá bí mật (N, d) được sử dụng làm khoá giải mã (Thuật toán 2). 
1.1.3. Hệ chữ ký số RSA 
Khoá bí mật (N, d) được sử dụng làm khoá sinh chữ ký (Thuật 
toán 3), và khoá công khai (N, e) được sử dụng làm khoá kiểm tra chữ ký 
(Thuật toán 4). 
1.1.4. An toàn của hệ mật RSA và phân tích số thách đố RSA 
 Hệ mật khóa công khai RSA có thể bị “phá vỡ” hoàn toàn nếu có 
thể phân tích được số modulo N. Độ phức tạp tính toán của NFS là 
1/3[1/3,(64/9) ]NL . Các tính chất của của tiểu hàm mũ này được nghiên 
cứu trong [2]. 
1.2. Phương pháp sàng trường số 
1.2.1. Xây dựng các hiệu bình phương 
Phương pháp sàng trường số NFS cần phải tìm một tập U các 
cặp (a, b) sao cho: 
2
( , )
( )
a b U
a b 
  , 2
( , )
( )
a b U
a bm y
  , 
với    và y . Sau đó, áp dụng kết quả đối với vành các số 
nguyên đại số: 
4 
2 2 2
( , ) ( , )
( ) ( ) ( ) ( )
a b U a b U
x a b a b       
     
  
 2
( , )
( ) (mod )
a b U
a bm y N
 
Khi đó, ta nhận được ước của N bằng cách tìm gcd(N, x±y).
 1.2.2. Tính trơn và các cơ sở phân tích 
Để tìm tập U ở trên, cần phải xây dựng các cơ sở phân tích, sau 
đó xét tính trơn trong các cơ sở phân tích đó. Cơ sở phân tích hữu tỷ 
RFB bao gồm các số nguyên tố nhỏ hơn một ngưỡng B nào đó. Cơ sở 
phân tích đại số AFB gồm hữu hạn các iđêan nguyên tố bậc nhất của 
  . Cơ sở đặc trưng bậc hai QCB gồm các iđêan nguyên tố bậc nhất 
tương ứng với các cặp (s, q) thỏa mãn '( ) 0 (mod )f s q . 
1.2.3. Tìm số chính phương đại số 
Phương pháp NFS dựa vào việc tìm các số chính phương trong 
 và   , nên sẽ cần phải tìm tập U các cặp quan hệ (a, b) trơn trong 
các cơ sở phân tích hữu tỷ RFB, cơ sở phân tích đại số AFB, và cơ sở đặc 
trưng bậc hai QCB. 
1.2.4. Chọn đa thức sàng 
1.2.4.1. Bài toán chọn đa thức sàng 
Bài toán. (Chọn đa thức sàng của Montgomery). Tìm các đa thức sàng 
bậc d>2 sao cho hệ số của chúng bằng O(N1/2d). 
1.2.4.2. Phương pháp chọn đa thức sàng tuyến tính 
Phương pháp base-m 
Cho 
 1/( 1) 1/d dN m N và 
  0 (0 )
d i
i ii
N a m a m là biểu 
diễn theo cơ số m của N. Thì khi đó 
1
1 0... , 
d d
d df x a x a x a g x x m 
là hai đa thức sàng có nghiệm chung m (mod N). 
5 
Phương pháp của Murphy 
Để đánh giá tính chất nghiệm của đa thức f, Murphy định nghĩa 
hàm 

log
1
1
p
p B
p
f q
p
 với B là cận trơn cho trước và qp là số 
nghiệm của  0 mod f x p . Nếu f càng nhỏ thì đa thức f x 
càng tốt cho phương pháp NFS. 
Phương pháp của Kleinjung 
Kleinjung đề xuất một cải tiến cho phương pháp của Murphy đối 
với đa thức không monic g: chọn một số nguyên dương ad có nhiều ước 
nguyên tố nhỏ và thỏa mãn  mod dda x N p với p nguyên tố. 
1.2.4.2. Phương pháp chọn đa thức sàng phi tuyến 
Phương pháp của Montgomery 
 Montgomery đã giải quyết bài toán chọn đa thức sàng với trường 
hợp d = 2, tìm được các cặp đa thức sàng có hệ số cỡ O(N1/4). 
Phương pháp của Prest và Zimmermann 
Prest và Zimmermann chọn các đa thức lệch bậc d tùy ý, nếu 
chọn độ lệch 
2
2
( 2)( )d d ds O N thì các đa thức có hệ số trung bình cỡ 
2
2
2 2
( 2)( )
d d
d d dO N . Koo và cộng sự đã tổng quát hóa các phương pháp xây 
dựng cấp số nhân mod N độ dài d+1 để chọn đa thức bậc bất kỳ có các 
hệ số cỡ 
2( 1) /( )d dO N . 
1.2.5. Sàng tìm quan hệ 
Chọn các cặp số nguyên (a, b) có các tính chất sau: 
 gcd(a, b)=1. 
 Chuẩn hữu tỷ a bm = a+bm là trơn trên RFB. 
 Chuẩn đại số  a b = (-b)deg(f)f(-a/b) là trơn trên AFB. 
6 
1.3. Kết luận chương 1 
Để làm nền tảng cơ sở cho các nội dung nghiên cứu tiếp theo, 
chương này của luận án đã trình bày tổng quan về các kết quả nghiên 
cứu đã được công bố có liên quan đến nội dung cần giải quyết của luận 
án. Cụ thể: 
 Giới thiệu về hệ mật khóa công khai RSA và độ an toàn của nó 
dựa vào việc giải bài toán phân tích số nguyên lớn; để thấy được 
sự cần thiết phải có những nghiên cứu về phương pháp phân tích 
số nguyên lớn nhanh nhất hiện nay, đó là phương pháp sàng 
trường số. 
 Tìm hiểu cơ sở lý thuyết của phương pháp sàng trường số, từ đó 
làm nền tảng để phát triển về lý thuyết, đánh giá và cài đặt thực 
hành phương pháp này. 
 Trên cơ sở tìm hiểu về bài toán chọn đa thức sàng của 
Montgomery và các phương pháp chọn đa thức sàng áp dụng 
cho phương pháp sàng trường số. Để từ đó làm tiền đề nghiên 
cứu phát triển thuật toán chọn cặp đa thức sàng bậc hai; xây 
dựng phương pháp và thuật toán chọn cặp đa thức sàng phi tuyến 
bậc ba; và đưa ra các thuật toán chọn cặp đa thức sàng bậc tổng 
quát cho phương pháp sàng trường số được trình bày trong 
Chương 2. 
 Trình bày chi tiết phương pháp sàng tìm quan hệ cho phương 
pháp sàng trường số. Từ đó có những cải tiến cài đặt thực hành 
cho phương pháp sàng trường số để phân tích thành công hợp số 
RSA; và đánh giá hiệu quả về mặt lý thuyết và thực hành của các 
thuật toán sàng áp dụng cho phương pháp sàng trường số được 
giải quyết trong Chương 3. 
7 
CHƯƠNG 2 
CHỌN CẶP ĐA THỨC SÀNG CHO PHƯƠNG PHÁP 
SÀNG TRƯỜNG SỐ 
2.1. Chọn cặp đa thức sàng bậc hai 
2.1.1. Thuật toán sinh các cặp đa thức sàng bậc hai 
Sử dụng thuật toán của Montgomery (Thuật toán 5) để sinh các 
cặp đa thức sàng bậc hai với các hệ số cỡ O(N1/4). 
2.1.2. Chọn cặp đa thức sàng bậc hai và tâm sàng 
Giả sử cặp đa thức sàng bậc hai f1(x) và f2(x) có 2 nghiệm tương 
ứng là x11, x12, x21, x22. Ta ký hiệu giá trị ρ(f1, f2) = min{|x1i-x2j |} là 
khoảng cách nhỏ nhất giữa các cặp nghiệm của 2 đa thức. Ta ký hiệu: 
1 2
1 2
0 min{| |}|
2 i j
i j
x x
x x
x 
là tâm sàng của cặp đa thức sàng bậc hai f1(x) và f2(x). 
Thực nghiệm 2.1. So sánh số quan hệ trung bình khi tâm miền sàng trục 
x tại điểm 0 và tại điểm x0 của các cặp đa thức sàng loại 1 (cặp đa thức 
sàng đồng thời có 2 nghiệm) và loại 2 (cặp đa thức sàng còn lại). Đối với 
các cặp đa thức loại 1 còn so sánh số quan hệ trung bình của các cặp đa 
thức sàng có giá trị ρ(f1, f2) nhỏ (đa thức loại 1a) và lớn (đa thức loại 1b). 
Bảng 2.1: Kết quả thực nghiệm 1. 
 Đa thức 
loại 2 
Đa thức 
loại 1a 
Đa thức 
loại 1b 
Số quan hệ trung bình với tâm 
miền sàng trục x tại điểm 0 
153 255 234 
Số quan hệ trung bình với tâm 
miền sàng trục x tại điểm x0 
- 836 657 
Khẳng định 2.1. Cặp đa thức sàng bậc hai đồng thời có hai nghiệm f1, f2 
được gọi là tốt hơn cho NFS nếu có giá trị ρ(f1, f2) nhỏ hơn. Khi đó, việc 
8 
chọn tâm điểm sàng trục x tại x0 là trung điểm của 2 nghiệm có ρ(f1, f2) 
nhỏ nhất sẽ tốt hơn là tâm sàng tại điểm 0. 
Theo quan điểm của Murphy thì cặp đa thức sàng f1, f2 được gọi 
là tốt hơn cho NFS nếu có giá trị (f1, f2) = (f1) + (f2) nhỏ hơn. 
Thực nghiệm 2.2. So sánh số quan hệ khi tâm miền sàng trục x tại điểm 
0 và tại điểm x0 của các cặp đa thức có ρmax, ρmin, max, min. 
Bảng 2.2: Kết quả thực nghiệm 2. 
 ρmax ρmin max min 
Số quan hệ TB với tâm 
miền sàng trục x tại điểm 0 
0 408 84 823 
Số quan hệ TB với tâm 
miền sàng trục x tại điểm x0 
230 910 245 1263 
Nhận xét 2.2. Cặp đa thức sàng có ρmin không tốt bằng cặp đa thức sàng 
có min mặc dù cặp đa thức này có giá trị ρ lớn hơn. 
Thuật toán 6: Thuật toán chọn cặp đa thức sàng bậc hai theo min và 
tâm sàng. 
Input: hợp số N. 
Output: cặp đa thức sàng bậc hai fi(x) và tâm sàng. 
Bước 1: Sinh tập các cặp đa thức sàng bậc hai theo phương pháp 
Montgomery. 
Bước 2: Chọn ra tập T các cặp đa thức sàng bậc hai đồng thời có 2 
nghiệm. 
Bước 3: Tìm min và tâm sàng x0 của cặp đa thức sàng trong tập T. 
Với mỗi cặp đa thức sàng ta ký hiệu: 
(f1, f2) = ' '1 2 1 1 2 2min ( ) (i j i jx x f x f x  
 Theo định nghĩa về đạo hàm thì sự biến thiên tại điểm sàng xs 
của 2 đa thức sàng ta nhận được: 
9 
(f1, f2) 1 2min ( ) (s sf x f x 
Thực nghiệm 2.3. So sánh số quan hệ trung bình của các cặp đa thức 
sàng bậc hai có 2 nghiệm tại tâm sàng x0 theo . 
Bảng 2.3: Kết quả thực nghiệm 3. 
Giá trị  
lớn nhất 
max 
Giá trị  
nửa cao 
H 
Giá trị  
nửa thấp 
L 
Giá trị  
nhỏ nhất 
min 
67 426 889 1183 
Khẳng định 2.2. Cặp đa thức sàng bậc hai đồng thời có hai nghiệm f1, f2 
được gọi là tốt hơn cho NFS nếu có giá trị (f1, f2) nhỏ hơn. 
Thuật toán 7: Thuật toán chọn cặp đa thức sàng bậc hai theo min và 
tâm sàng. 
Input: hợp số N. 
Output: cặp đa thức sàng bậc hai fi(x). 
Bước 1: Sinh tập các cặp đa thức sàng bậc hai theo phương pháp 
Montgomery. 
Bước 2: Chọn ra tập T các cặp đa thức sàng bậc hai đồng thời có 2 
nghiệm. 
Bước 3: Tìm min và tâm điểm sàng tối ưu x0 tương ứng trong tập T. 
2.1.3. Một số nhận xét 
Kết quả của các thực nghiệm trên đã đưa ra được 2 thuật toán 
lựa chọn cặp đa thức sàng bậc hai và tâm sàng của chúng cho NFS. 
Trong đó, khi phân tích số nguyên lớn thì Thuật toán 7 sẽ nhanh hơn 
đáng kể so với Thuật toán 6 mà vẫn đảm bảo chọn ra được cặp đa thức 
sàng tốt gần tương đương. Kết quả này thực sự quan trọng khi thực hiện 
việc chọn cặp đa thức sàng để phân tích các số nguyên lớn. 
10 
2.2. Chọn cặp đa thức sàng bậc ba 
2.2.1. Xây dựng cơ sở lý thuyết chọn cặp đa thức sàng bậc ba 
2.2.1.1 Một số khái niệm 
Khái niệm về không gian Euclid trên ℝm. 
Định nghĩa về tích có hướng của 3 véc tơ trong ℝ4. 
Định nghĩa 2.1. (tích có hướng của 3 véc tơ) Cho 3 véc tơ 
 = 0 1 2 3, , ,a a a a , = 0 1 2 3, , ,b b b b và = 0 1 2 3, , ,c c c c . Ta gọi tích có 
hướng của chúng là véc tơ, ký hiệu là   , được xác định bởi công 
thức sau 
   = 
1 2 3 0 2 3 0 1 3 0 1 2
1 2 3 0 2 3 0 1 3 0 1 2
1 2 3 0 2 3 0 1 3 0 1 2
a a a a a a a a a a a a
b b b , b b b , b b b , b b b
c c c c c c c c c c c c
. 
 Từ định nghĩa trên ta xây dựng các tính chất cơ bản sau. 
2.2.1.2 Các tính chất cơ bản 
Tính chất 2.1. Nếu  =   thì   ,    và   . 
Tính chất 2.2. Tích có hướng của 3 véc tơ là tuyến tính với mỗi véc tơ 
của tích, chẳng hạn với ,k h thì 
 (k +h ’)  = k(  ) + h( ’  ). 
Tính chất 2.3. 
1) Đổi thứ tự hai véc tơ cạnh nhau thì tích có hướng của 3 véc tơ 
đổi dấu, chẳng hạn 
  = (  ). 
2) Nếu tích có hướng của 3 véc tơ trong đó có hai véc tơ giống 
nhau thì nhận được véc tơ không. 
Từ các tính chất trên ta thu được bổ đề quan trọng dưới đây. 
11 
Bổ đề 2.1. Giả sử 
1 2 3
1 2 3
1 2 3
' ' '
' ' '
' ' '
u u u
v v v
w w w
  
  
  
, với , ,i i iu v w , i = 1, 2, 
3 ta có: 
 det( A) ' ' '    
trong đó A = 
1 2 3
1 2 3
1 2 3
u u u
v v v
w w w
. 
Định lý 2.1 dưới đây đưa ra một điều kiện cần và đủ để tích có 
hướng của 3 véc tơ   =  trên không gian ℤ4. 
Định lý 2.1. Cho 4 véc tơ khác véc tơ không , ,  và  ℤ4, ta có: 
   =  khi và chỉ khi span( ,,) = {}. 
Định lý 2.2 dưới đây đưa ra công thức cho phép xác định chuẩn 
của véc tơ tích có hướng của 3 véc tơ trên không gian ℤ4. 
Định lý 2.2. Ký hiệu A, B, C là các góc giữa và , giữa  và , giữa  
và thì 
   = 2 2 21 2cos Acos BcosC cos A cos B cos C   . 
Tuy nhiên, việc xác định chuẩn theo công thức trong Định lý 2.2 
là rất phức  ... hệ số nhỏ. 
Do các đa thức A(x), B(x), và C(x) có các hệ số cỡ O(N2/9), nên các hệ số 
của đa thức f(x) cũng có độ lớn cỡ O(N2/9). 
2.2.3. Một số nhận xét 
Dựa vào cơ sở lý thuyết mới xây dựng cho phép ta chọn được 
cặp đa thức sàng bậc ba các hệ số cỡ O(N2/9) cho phương pháp sàng 
trường số. 
Trong khi đó, phương pháp của Prest và Zimmermann tạo ra cặp 
đa thức sàng bậc 3 với các hệ số trung bình cỡ O(N5/24), do xét đến điều 
kiện về độ lệch của các đa thức sàng. 
Thuật toán 8 có thể sinh ra được rất nhiều cặp đa thức sàng phi 
tuyến bậc 3 cho NFS, tùy thuộc vào cách chọn K. Nhưng không phải tất 
cả các cặp đa thức sàng đó đều tốt cho phương pháp NFS nên có thể cần 
phải xét thêm hàm f của Murphy. 
2.3. Chọn cặp đa thức sàng bậc tổng quát 
2.3.1. Chọn cặp đa thức sàng dựa vào cấp số nhân 
2.3.1.1 Một số khái niệm cơ bản 
 Rút gọn lưới và chuẩn của véc tơ. 
 Kết quả đã biết về tích chập. 
15 
2.3.1.2 Chọn cặp đa thức dựa vào cấp số nhân 
Mệnh đề 2.1. Cho trước số nguyên N và cấp số nhân 0 1, ,..., dc c c có d+1 
số hạng công bội m và thỏa mãn 0 (mod )
i
ic c m N , thì có thể sinh ra d 
đa thức bậc tối đa d có nghiệm chung m modulo N có hệ số cỡ 1/ dc với 
max| |ic c . 
2.3.2. Xây dựng thuật toán chọn cặp đa thức sàng bậc tổng quát 
2.3.2.1 Chọn cấp số nhân 
Hệ quả 2.2. Cho trước số nguyên N và cấp số nhân 1, ,..., dm m N 
modulo N có công bội 1/ dm N , thỏa mãn rằng ( 1) /( )d d dm N O N , 
thì có thể sinh ra cặp đa thức bậc d có nghiệm chung m modulo N với 
các hệ số cỡ 
2( 1) /( )d dO N và tích chập cỡ 2( 1) /( )d dO N . 
Xây dựng ma trận có dạng như sau: 
1 2 1
1 0 0 0
0 1 0 0
0 0 0 0
0 0 1 0
0 0 0 1
d d
L
c c c c 
Ta chứng minh được rằng sau khi thực hiện thuật toán LLL đối 
với ma trận L sẽ tìm ra tối thiểu 2 véc tơ ngắn có hệ số cỡ 
2( 1) /( )d dO N . 
2.3.2.2 Thuật toán chọn cặp đa thức sàng bậc tổng quát 
Từ Hệ quả 2.2, cho ta thuật toán sinh đa thức sàng phi tuyến bậc 
d như sau. 
Thuật toán 10: Thuật toán sinh cặp đa thức sàng phi tuyến bậc d. 
Input: Số nguyên cần phân tích N, bậc d. 
Output: Cặp đa thức sàng f1 và f2 bậc d có nghiệm chung m modulo N. 
16 
(1). Tính 1/ dm N 
. 
(2). Tạo cấp số nhân 1, ,..., dm m N . 
(3). Sử dụng thuật toán LLL đối với ma trận L để tìm các véc tơ ngắn 
1( ,..., )db b . 
(4). Biểu diễn ,0 ,( ,..., )
t
i i i da a b và tính ,0 ,1 mod
d j
i i jj
a a m N
  , với 
i = 1, 2. 
(5). Trả về cặp đa thức ,0
d j
i i jj
f a x
  và nghiệm chung m mod N. 
Về mặt thực hành, việc thực hiện bước kiểm tra các hệ số đầu và 
hệ số cuối có ước nguyên tố nhỏ trước khi áp dụng ( )iF và phép xoay 
đa thức của Murphy sẽ loại bỏ được rất nhiều đa sàng có tính chất tồi. 
Thuật toán 11: Thuật toán chọn cặp đa thức phi tuyến bậc d tốt. 
Input: Số nguyên cần phân tích N, bậc của cặp đa thức phi tuyến d, 
 ngưỡng của phép xoay đa thức J. 
Output: Cặp đa thức sàng (f1, f2) có tính chất tốt. 
(1). Sử dụng Thuật toán 10 sinh cặp đa thức phi tuyến (f1, f2) bậc d có 
nghiệm chung m modulo N. 
(2). Kiểm tra các hệ số đầu và cuối là bội của 60. 
(3). Tính ( )if và ghi vào tệp “Alphas.txt”. 
(4). Thực hiện phép xoay đa thức với 1 2 3, , (0, ]j j j J : 
(4).1 
1 2 3, , 1 1 2 2 3
( ) ( ) ( ) ( )j j jf x j f x j f x j x m . 
(4).2 Tính 
1 2 3, ,
( )j j jf , ghi vào tệp “Alphas.txt”. 
(5). Return “Cặp đa thức fi có nghiệm chung m modulo N có giá trị 
( )if nhỏ nhất trong tệp Alphas.txt”. 
2.3.3. Một số nhận xét 
Áp dụng Hệ quả 2.2 thì: 
17 
 Có thể sinh ra cặp đa thức sàng bậc 2 có nghiệm chung m modulo N 
với các hệ số cỡ 1/ 4( )O N và tích chập cỡ ( )O N . Kết quả này trùng 
với phương pháp của Montgomery. 
 Có thể sinh ra cặp đa thức sàng bậc 3 có nghiệm chung m modulo N 
với các hệ số cỡ 2 / 9( )O N và tích chập cỡ 4 / 3( )O N . Kết quả này 
trùng với phương pháp luận án đã xây dựng. 
 Có thể sinh ra cặp đa thức bậc d = 4 có nghiệm chung m modulo N 
với các hệ số cỡ 3/16( )O N và tích chập cỡ 3/ 2( )O N . Kết quả này 
tốt hơn phương pháp của Prest và Zimmermann sinh ra các đa thức 
có hệ số cỡ 5/14( )O N và tích chập cỡ 10 / 7( )O N . 
2.4. Kết luận chương 2 
Các kết quả của chương này bao gồm: 
(1). Đưa ra các Thuật toán 6 và Thuật toán 7 để chọn cặp đa thức sàng 
bậc hai và tâm sàng của chúng cho phương pháp sàng trường số. 
Thuật toán 7 thực hiện nhanh hơn Thuật toán 6; việc sàng tìm quan 
hệ tại tâm sàng sẽ giúp cho phương pháp NFS thực hiện nhanh hơn. 
(2). Xây dựng phương pháp và cơ sở lý thuyết (bao gồm: Định lý 2.1, 
Định lý 2.2, và Hệ quả 2.1) cho thuật toán chọn cặp đa thức sàng phi 
tuyến bậc ba cho phương pháp sàng trường số. Kết quả thu được 
Thuật toán 8, dùng để tìm các cặp đa thức sàng phi tuyến bậc 3 có 
các hệ số cỡ O(N2/9); góp phần giải trường hợp riêng của bài toán 
chọn đa thức sàng Montgomery. 
(3). Tổng quát hóa thuật toán chọn cặp đa thức sàng dựa vào cấp số nhân 
đặc biệt, từ đó xây dựng được Thuật toán 10 và Thuật toán 11 để 
chọn cặp đa thức sàng phi tuyến bậc tổng quát. 
Các kết quả nêu trên đã được tác giả công bố trên các bài báo số [1], 
[4], và [6] (Danh mục các công trình khoa học đã công bố). 
18 
CHƯƠNG 3 
CẢI TIẾN VÀ ĐÁNH GIÁ HIỆU QUẢ THUẬT TOÁN SÀNG 
CHO PHƯƠNG PHÁP SÀNG TRƯỜNG SỐ 
3.1. Thuật toán NFS tổng quát 
Thuật toán 12: Thuật toán NFS tổng quát. 
Input: Hợp số N. 
Output: Ước không tầm thường p của N. 
Bước 1: Chọn đa thức sàng. 
Bước 2: Xây dựng các cơ sở phân tích. 
Bước 3: Sàng tìm quan hệ. 
Bước 4: Giải hệ phương trình đại số tuyến tính. 
Bước 5: Khai căn bậc hai và tìm ước. 
3.2. Cải tiến cài đặt thuật toán sàng tuyến tính 
3.2.1. Thuật toán sàng tuyến tính 
Thuật toán sàng tuyến tính (Thuật toán 13) gồm 2 bước chính: 
 Các phần tử (a, b) có chuẩn hữu tỷ chia hết cho (p, m mod p) 
trong RFB thì a có dạng a = -bm+kp với k . 
 Các phần tử (a, b) có chuẩn đại số chia hết cho (p, r) trong 
AFB thì a có dạng a = -br+kp với k . 
3.2.2. Song song hóa thuật toán sàng tuyến tính 
Giả sử thực hiện thuật toán trên M tiến trình, tiến trình t thực 
hiện sàng với các giá trị b trong khoảng WS*(t-1) đến WS*t. Sau khi tất 
cả các tiến trình kết thúc việc sàng trong khoảng WS đã xác định thì lặp 
lại công việc sàng của các tiến trình như trên với giá trị b mới bắt đầu từ 
WS*M. Công việc này được thực hiện lặp lại đối với các tiến trình đến 
19 
khi nhận đủ các quan hệ cần tìm. Khi đó bước sàng tìm quan hệ sẽ kết 
thúc. 
Thuật toán 14: Thuật toán sàng tuyến tính phiên bản song song cho 
tiến trình thứ t. 
Input: - Các cơ sở phân tích RFB, AFB; 
 - Đa thức f(x), nghiệm m của f(x) mod N; 
 - Khoảng sàng C; 
 - WS, t, b0: trong đó b0 là giá trị đầu tiên của b cho tiến trình 
 thứ t với số lượng giá trị cần sàng WS. 
Output: - Tập quan hệ rels = {(a0, b0), (a1, b1),, (al, bl)}. 
1. b= b0+WS*(t-1) 
2. rels=[] 
3. while ((b b0+WS*t) and (#rels < #RFB + #AFB + #QCB + 1)) 
(a) b=b+1 
(b) a[i]=i+bm với i [-C;C] 
(c) với mỗi (p, r) RFB 
Chia a[j] cho p tối đa số mũ có thể với j=-bm+kp 
với k thỏa mãn –C j C. 
(d) e[i]=(-b)deg(f)f(-i/b) với i [-C;C] 
(e) với mỗi (p, r) AFB 
Chia e[j] cho p tối đa số mũ có thể với j=-br+kp 
với k thỏa mãn –C j C. 
(f) for i [-C;C] 
if a[i]=e[i]=1 và gcd(i, b)=1 thêm (i, b) vào rels 
4. return rels. 
20 
3.2.3. Kết quả phân tích số 135 chữ số 
Hệ thống tính toán hiệu tại Học viện Kỹ thuật mật mã là hệ 
thống tính toán với bộ nhớ phân tán. Tích hợp thuật toán 14 ở trên vào 
chương trình msieve phiên bản 1.21 để phân tích số nguyên hợp số N có 
135 chữ số thập phân. Kết quả là: 
 Thời gian lựa chọn đa thức là 29 giờ. 
 Tổng số tiến trình t = 112, và khoảng sàng WS = 2000000. Tổng 
thời gian sàng là 6,66 ngày. Thời gian chạy tổng cộng của tất cả 
các tiến trình: 64489521 giây = 746 ngày. 
3.3. Đánh giá hiệu quả của thuật toán sàng lưới 
3.3.1. Thuật toán sàng lưới 
3.3.1.1. Hoạt động của sàng lưới 
Phần tử mảng A[c, d] biểu diễn số nguyên: 
1 2a bm c u d u   , với 1 1 1u a b m và 2 2 2u a b m . 
Do đó các phần tử để được sàng với p khi: 
 1 2 0 mod c u d u p   . 
3.3.1.2. Cài đặt thuật toán sàng lưới cho NFS 
Với mỗi ,q s Q thực hiện: 
 Xác định lưới của (a, b) tương ứng với mod a bs q . 
 Xây dựng các trục tọa độ (c, d) cỡ C cho lưới này. 
 Với mỗi ,p r P chuyển mod a br p về mặt phẳng (c, d). 
 Với mỗi miền sàng của mặt phẳng (c, d) kiểm tra tính trơn của 
cặp (c, d). 
3.3.2. Kết quả quan trọng về lý thuyết lưới 
Bổ đề 3.1. m là một lưới khi và chỉ khi là một tập rời rạc, 
nhóm con cộng tính của m . 
Luận án phát biểu mệnh đề tổng quát với lưới n chiều như sau. 
21 
Mệnh đề 3.1. Giả sử 1 2( , ,..., ) \ 0
n
n và q . ,q là tập 
hợp xác định như sau: 
 , | , 0 (mod )nq x x q  
(trong đó .,. là một tích vô hướng chuẩn tắc). Khi đó, ,qL là lưới 
trong n và thỏa mãn: 
,
1 2
det
gcd( , ,..., , )
q
n
q
q
3.3.3. Hiệu quả của thuật toán sàng lưới 
3.3.3.1. Khẳng định của Pollard 
Các quan hệ ,a b sẽ tạo thành một lưới con ,q trong 
2 với 
 21,m và q là số nguyên tố. Sử dụng Mệnh đề 3.1 với lưới 2 
chiều để chứng minh Khẳng định 3.1 của Pollard. 
Khẳng định 3.1 (của Pollard). Trong NFS, tổng số các số nguyên cần 
phải sàng theo thuật toán sàng lưới nhỏ hơn rất nhiều so với thuật toán 
sàng tuyến tính. Thực tế, nó có thể giảm theo hệ số: 
 1
log 1/1
logq M
k
W
q B 
  . 
3.3.3.2. Phân tích một số kết quả thực nghiệm 
Bảng 3.1. Hiệu suất của thuật toán sàng tuyến tính. 
Khoảng 
sàng 
Số lượng 
quan hệ 
Số lượng số 
kiểm tra 
H 
2000x2000 113.290 4.000.000 2,832.10-2 
3000x3000 220.345 9.000.000 2,448.10-2 
4000x4000 353.298 16.000.000 2,208.10-2 
5000x5000 508.540 25.000.000 2,034.10-2 
Kết quả thực hiện thuật toán sàng lưới thay đổi theo ki, với k1 = 
0,447, k2 = 0,269, k3 = 0,160. 
22 
Bảng 3.2. Thuật toán sàng lưới thay đổi theo ki, i = 1, 2, 3. 
Khoảng 
sàng 
Số lượng quan hệ Số lượng số kiểm tra 
k1 k2 k3 k1 k2 k3 
2000x2000 47.338 71.285 112.403 607.285 1.010.887 1.774.362 
3000x3000 96.426 144.494 196.896 1.365.960 2.273.003 3.318.761 
4000x4000 159.065 237.819 323.660 2.428.342 4.043.587 5.902.669 
5000x5000 233.919 349.359 475.143 3.794.283 6.320.513 9.225.408 
Bảng 3.3. Hiệu suất của thuật toán sàng lưới. 
Khoảng sàng H 
k1 k2 k3 
2000x2000 7,795.10-2 7,051.10-2 6,330.10-2 
3000x3000 7,059.10-2 6,356.10-2 5,932.10-2 
4000x4000 6,550.10-2 5,881.10-2 5,483.10-2 
5000x5000 6,165.10-2 5,527.10-2 5,150.10-2 
0
1
2
3
4
5
6
7
8
9
2000x2000 3000x3000 4000x4000 5000x5000
k=0,447
k=0,269
k=0,160
line
Hình 3.1: So sánh hiệu suất của 2 thuật toán sàng. 
23 
Nhận xét 3.1. 
 Tính được hệ số giảm giữa lượng số nguyên đem sàng của thuật toán 
sàng lưới so với thuật toán sàng tuyến tính theo ki là hoàn toàn đúng 
theo công thức của Pollard. 
 Tỷ lệ số lượng quan hệ tìm được trên số lượng số cần kiểm tra giảm 
đi rất nhiều (thuật toán sàng lưới nhanh hơn khoảng 3 lần thuật toán 
sàng tuyến tính). 
 Khi tăng khoảng sàng thì hiệu suất của cả 2 thuật toán đều bị giảm. 
 Trong thuật toán sàng lưới, hệ số ki giảm làm cho hiệu suất giảm. 
Khi ki ≈ 0 thì thuật toán sàng lưới gần như trở thành thuật toán sàng 
tuyến tính. 
3.4. Kết luận chương 3 
Các kết quả của chương này bao gồm: 
(1). Đã cải tiến song song thuật toán sàng tuyến tính (Thuật toán 14) trên 
một hệ thống tính toán cụ thể để phân tích hợp số RSA cỡ 135 chữ 
số thập phân. Kết quả phân tích là một minh chứng cho việc cải tiến 
thành công về mặt thực hành phương pháp sàng trường số và có thể 
triển khai cài đặt trên các hệ thống tính toán lớn để đánh giá, phân 
tích độ an toàn của hệ mật khóa công khai RSA. 
(2). Đã đánh giá hiệu quả của thuật toán sàng lưới của Pollard: Sử dụng 
lý thuyết lưới để phát biểu và chứng minh Mệnh đề 3.1 đối với 
trường hợp số chiều tổng quát n chiều, áp dụng kết quả này để chứng 
minh phát biểu của Pollard với trường hợp 2 chiều. Thực hành cài 
đặt so sánh hiệu suất giữa hai phương pháp sàng, đã thu được các kết 
quả chính xác phù hợp với lý thuyết. 
Các kết quả nêu trên đã được tác giả công bố trên các bài báo số [3] 
và [5] (Danh mục các công trình khoa học đã công bố). 
24 
KẾT LUẬN 
Những đóng góp mới của Luận án: 
1. Phát triển thuật toán chọn cặp đa thức sàng bậc hai và tâm sàng cho 
phương pháp sàng trường số. Cụ thể, đưa ra các Thuật toán 6 và 
Thuật toán 7 để chọn cặp đa thức sàng bậc hai tốt và tâm sàng của 
chúng từ đó có thể nhận được nhiều quan hệ hơn làm giảm thời gian 
sàng cho phương pháp sàng trường số. 
2. Xây dựng phương pháp và thuật toán chọn đa thức sàng phi tuyến 
bậc ba, góp phần giải trường hợp riêng của bài toán mở 
Montgomery. Kết quả thu được là xây dựng được cơ sở lý thuyết 
(Định lý 2.1, Định lý 2.2, và Hệ quả 2.1) cho Thuật toán 8, dùng để 
tìm các cặp đa thức sàng phi tuyến bậc 3 có các hệ số cỡ O(N2/9) cho 
phương pháp sàng trường số. 
3. Đánh giá hiệu quả về mặt lý thuyết và thực hành thuật toán sàng lưới 
của Pollard áp dụng cho phương pháp sàng trường số. Đã đưa ra 
Mệnh đề 3.1 phát biểu cho lưới tổng quát n chiều, từ đó áp dụng kết 
quả này để chứng minh phát biểu của Pollard với trường hợp 2 
chiều. Thực hành cài đặt so sánh hiệu suất giữa hai phương pháp 
sàng, đã thu được các kết quả chính xác phù hợp với lý thuyết. 
Hướng nghiên cứu tiếp theo: 
- Nghiên cứu phương pháp chọn đa thức sàng phi tuyến có hệ số lệch 
và có tính chất tốt cho phương pháp sàng trường số. 
- Thiết kế song song hóa các thuật toán cho phương pháp sàng trường 
số, triển khai cài đặt trên các hệ thống tính toán lớn. 
- Áp dụng phương pháp sàng trường số giải bài toán phân tích số và 
tính logarit rời rạc nhằm đánh giá các hệ mật có độ an toàn dựa vào 
các bài toán này. 
25 
DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ 
1. Đinh Quốc Tiến, Lều Đức Tân (2011), “Tìm đa thức sàng bậc 3 cho 
phương pháp sàng trường số”, Tạp chí Nghiên cứu Khoa học và 
Công nghệ quân sự, số 14/08-2011, tr. 63-70. 
2. Đinh Quốc Tiến (2011), “Hàm Lp[α;c] trong đánh giá độ phức tạp 
tính toán”, Tạp chí Nghiên cứu Khoa học và Công nghệ quân sự, số 
14/08-2011, tr. 71-76. 
3. Phạm Việt Trung, Đinh Quốc Tiến, Phạm Văn Lực (2011), “Cải tiến 
phương pháp sàng trường số tổng quát và thực hiện trên hệ thống 
tính toán hiệu năng cao”, Tạp chí Nghiên cứu Khoa học và Công 
nghệ quân sự, số đặc san 11-2011, tr. 53-59. 
4. Đinh Quốc Tiến (2012), “Khảo sát tính B-trơn của đa thức sàng bậc 
hai sử dụng cho phương pháp sàng trường số”, Tạp chí Nghiên cứu 
Khoa học và Công nghệ quân sự, số đặc san 05-2012, tr. 22-29. 
5. Phạm Việt Trung, Nguyễn Bùi Cương, Đinh Quốc Tiến (2012), “Về 
phương pháp sàng lưới áp dụng cho sàng trường số”, Tạp chí 
Nghiên cứu Khoa học và Công nghệ quân sự, số đặc san 05-2012, tr. 
30-37. 
6. Lều Đức Tân, Phạm Việt Trung, Đinh Quốc Tiến (2013), “Về thuật 
toán chọn đa thức sàng phi tuyến tổng quát cho phương pháp sàng 
trường số”, Tạp chí Nghiên cứu Khoa học và Công nghệ quân sự, số 
đặc san 05-2013, tr. 05-13.