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ã

p là số 
 pB p 1
nghiệm của f x  0 mod p . Nếu f càng nhỏ thì đa thức fx 
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 
 d
nguyên tố nhỏ và thỏa mãn ad x N mod 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 
 2
 2
chọn độ lệch s O() N d( d d 2) thì các đa thức có hệ số trung bình cỡ 
 dd2 22
 2
ON()d( d d 2) . 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 
 2
hệ số cỡ ON()(dd 1)/ . 
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ố ab  = (-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: 
 xx12ij 
 x | 
 02 min{|xx12ij |}
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 Đa thức Đa thức 
 loại 2 loại 1a loại 1b 
 Số quan hệ trung bình với tâm 153 255 234 
 miền sàng trụcx tại điểm 0 
 Số quan hệ trung bình với tâm - 836 657 
 miền sàng trụcx tại điểmx 0 
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 0 408 84 823 
 miền sàng trụcx tại điểm 0 
 Số quan hệ TB với tâm 230 910 245 1263 
 miền sàng trụcx tại điểmx 0 
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: 
 minx x  f'' ( x ) f ( x
 (f1, f2) = 1i 2 j 1 1 i 2 2 j  
 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) min f12 ( xss ) 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ị Giá trị Giá trị Giá trị 
 lớn nhất nửa cao nửa thấp nhỏ nhất 
 max H L 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ơ 
 = a0,,, a 1 a 2 a 3 , = b0,,, b 1 b 2 b 3 và = c0,,, c 1 c 2 c 3 . 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 
 aaa123 aaaaaa 023013 aaa 012
 = bb123 b,b 023013 b b,b bb,b 012 bb . 
 ccc123 cccccc 023013 ccc 012
 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 kh, 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 
 u1 ''' u 2  u 3 
Bổ đề 2.1. Giả sử  v1 ''' v 2  v 3  , với ui,, v i w i , i = 1, 2, 
  w1 ''' w 2  w 3 
3 ta có: 
   det( A) '  '  ' 
 u1 u 2 u 3
trong đó A = v1 v 2 v 3 . 
 w1 w 2 w 3
 Đị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ì 
   =   12 cos Acos BcosC cos222 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 tạp. Hệ quả 2.1 dưới đây cho phép ta xác định cận dưới của 
chuẩn tích có hướng của 3 véc tơ trên ℤ4 áp dụng cho một số trường hợp 
góc A, B, C đặc biệt. 
 2
Hệ quả 2.1. Nếu các góc A, B, C , và số các góc tù là chẵn thì 
 33
 1
     . 
 2
2.2.2. Thuật toán chọn cặp đa thức sàng bậc ba 
 Thuật toán 8: Thuật toán chọn cặp đa thức sàng bậc ba. 
 Input: hợp số N. 
 12 
 2/9
 Output: cặp đa thức sàng bậc ba fi(x) có các hệ số cỡ ON(). 
 Bước 1: Tìm  4 có tọa độ là cấp số nhân theo modulo N. 
 Bước 2: Tìm cơ sở ban đầu { ’, ’,’} của lưới L = {}. 
 Bước 3: Rút gọn cơ sở ban đầu để được cơ sở “nhỏ nhất” { , , }. 
 Bước 4: Tìm các đa thức có hệ số nhỏ tương ứng với véc tơ tổ hợp 
 tuyến tính của , , . 
2.2.2.1. Tìm  có tọa độ là cấp số nhân theo modulo N. 
 Chọn số nguyên tố p = O(N1/3) sao cho p = 3r +1 và N r  1 
 bN3 
(mod p), a = và b = O(N1/3). Ta tìm được  = (a,b2,bp,p2), thỏa 
 p
mãn |||| = O(N2/3). 
2.2.2.2. Tìm cơ sở ban đầu cho L = {}. 
 Theo định lý 2.1 ta tìm cơ sở của L là tìm 3 véc tơ , ,  thỏa 
mãn   =  như sau: 
 = (-b2, a, 0, 0). 
 p b2 s bp
  = (t, -s, 1, 0), với s ≡ (mod a) và t = . 
 b a
 b22 u p
  = (v, -u, 0, 1), với u ≡ s2 (mod a) và v = . 
 a
2.2.2.3. Thuật toán rút gọn cơ sở lưới. 
 Thuật toán 9: Thuật toán rút gọn cơ sở lưới. 
 Input: { ’, ’, ’} là 3 véc tơ độc lập tuyến tính trong ℤ4. 
 Output: { , , } thoả mãn các điều kiện sau: 
   = '''   
 || ||×||||×|||| < 2   . 
 1.[Initiliatian] 
 { , , } = { ’, ’, ’}; Continue = 1; 
 2.[Loop] 
 13 
 While (Continue = 1) { 
 Continue = 0; 
 InOrder{ , , }; //sắp xếp giảm dần 
 ,
 q  ; 
 ,
 if (q>0) {  q; Continue = 1;} 
 else { 
 ,
 q  ; 
 ,
 if (q>0) {  q; Continue = 1;} 
 ,
 q  ; 
 ,
 if (q>0) {   q; Continue = 1; } 
 } 
 Return { , , }. 
Nhận xét 2.3. Vòng lặp 2 sẽ dừng chỉ khi tất cả các giá trị q tính được 
trong đó đều bằng 0 và cũng giống như thuật toán của Montgomegy ta có 
 2
tất cả các góc giữa các cặp véc tơ đầu ra đều nằm trong đoạn , . 
 33
Hệ quả 2.1 của định lý 2.2 cho phép đánh giá trong trường hợp số góc tù 
chẵn là: 
   2  = O(N2/3). 
 Khi các véc tơ tại đầu ra có chuẩn xấp xỉ nhau ta có chuẩn của 
các véc tơ này cỡ O(N2/9), tức là: 
   ON()2/9 . 
2.2.2.4. Chọn cặp đa thức sàng 
 
 Giả sử cơ sở rút gọn của {} là = (a0, a1, a2, a3),  = (b0, b1, 
b2, b3) và =(c0, c1, c2, c3). Ký hiệu 
 14 
 23
 A(x) a0 ax 1 ax 2 ax 3 . 
 23
 B(x) b0 bx 1 bx 2 bx 3 . 
 23
 C(x) c0 cx 1 cx 2 cx 3 . 
 Lấy một ngưỡng K nào đó ta tìm tất cả các đa thức bất khả quy 
 f
trên ℤ trong tập 
 {uA(x) + vB(x) + wC(x): -K u, v, w K} 
 Cuối cùng so sánh để chọn ra cặp đa thức sàng có cá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 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 c01, c ,..., cd có d+1 
 i
số hạng công bội m và thỏa mãn ci c0 m(mod 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ỡ c1/d với 
cc max|i |. 
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,m ,..., md N 
modulo N có công bội mN 1/d , thỏa mãn rằng md N O() N ( d 1) / d , 
thì có thể sinh ra cặp đa thức bậc d có nghiệm chung m modulo N với 
 2
các hệ số cỡ ON()(dd 1) / và tích chập cỡ ON()2(dd 1) / . 
 Xây dựng ma trận có dạng như sau: 
 1 0 0 0
 0 1 0 0
 0 0 0 0
 L 
 0 0 1 0
 0 0 0 1
 c1 c 2 cdd 1 c
 Ta chứng minh được rằng sau khi thực hiện thuật toán LLL đối 
 2
với ma trận L sẽ tìm ra tối thiểu 2 véc tơ ngắn có hệ số cỡ ON()(dd 1) / . 
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/d
 (1). Tính mN . 
 (2). Tạo cấp số nhân 1,m ,..., md 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 
 (bb1 ,...,d ) . 
 d
 (4). Biểu diễn b (aa ,..., )t và tính a a mj mod N , với 
 i i,0 i , d i,0 j 1 i , j
 i = 1, 2. 
 d
 (5). Trả về cặp đa thức f a x j và nghiệm chung m mod N. 
 i j 0 i, j
 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 ()Fi 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 ()fi và ghi vào tệp “Alphas.txt”. 
 (4). Thực hiện phép xoay đa thức với j1, j 2 , j 3 (0, J ] : 
 (4).1 f()()()() x jfxjfxjxm . 
 j1, j 2 , j 3 1 1 2 2 3
 (4).2 Tính ()f , ghi vào tệp “Alphas.txt”. 
 j1,, j 2 j 3
 (5). Return “Cặp đa thức fi có nghiệm chung m modulo N có giá trị 
 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ỡ ON()1/ 4 và tích chập cỡ ON(). 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ỡ ON()2 / 9 và tích chập cỡ ON()4 / 3 . 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ỡ ON()3/16 và tích chập cỡ ON()3/ 2 . 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ỡ ON()5/14 và tích chập cỡ ON()10 / 7 . 
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: 
 a bm c  u12 d  u , với u1 a 1 b 1 m và u2 a 2 b 2 m . 
 Do đó các phần tử để được sàng với p khi: 
 c u12 d  u  0 mod 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 a bs mod 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 a br mod 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 
 n
Mệnh đề 3.1. Giả sử ( 12 , ,..., n ) \ 0 và q . ,q là tập 
hợp xác địn