Xây dựng một phương pháp sinh số nguyên tố tất định

Công nghệ thông tin & Khoa học máy tính L.V. Tuấn, B.T. Truyền, “Xây dựng một phương pháp sinh số nguyên tố tất định.” 146 XÂY DỰNG MỘT PHƯƠNG PHÁP SINH SỐ NGUYÊN TỐ TẤT ĐỊNH Lê Văn Tuấn*, Bùi Thế Truyền Tóm tắt: Trong bài báo này, chúng tôi đề xuất một thuật toán sinh số nguyên tố tất định. Thuật toán này được xây dựng dựa trên một số thuật toán sinh số nguyên tố đã có. Điều quan trọng là lực lượng số nguyên tố được tạo ra bằng thuật toán mới sẽ lớn hơn so với lực lượng các số nguyên tố được tạo ra từ thuật toán trước đó, và thuật toán mới này còn đưa ra “kiểu bằng chứng” về tính nguyên tố của nó. Từ khóa: Mật mã khóa công khai, Chữ ký số. 1. MỞ ĐẦU Số nguyên tố được ứng dụng rất nhiều trong thực tế, đặc biệt chúng là một trong những tham số quan trọng trong các hệ mã khoá công khai, chẳng hạn như: Hệ mã RSA, hệ mã Elgamal hay hệ mã ECC ... Hơn nữa số nguyên tố còn là tham số của các hệ chữ ký số được xây dựng trên nền tảng hệ mật khóa công khai. Vì thế, việc xây dựng những thuật toán mới để sinh các số nguyên tố hiệu quả hơn các thuật toán đã có là một nhu cầu rất cần thiết. Trên thực tế thường sử dụng hai phương pháp sinh số nguyên tố phổ biến, đó là “phương pháp xác suất” và “phương pháp chứng minh được”. Những phương pháp sinh số nguyên tố này đã được áp dụng trong một số chuẩn của thế giới như: [ANSI X9.31], [FIP 186.3], [TCVN 7635; 2007], [ISO/IEC 18032;2004], v.v.. Các số nguyên tố được sinh ra theo phương pháp thứ nhất khác với phương pháp thứ hai là không đưa ra được “bằng chứng để chứng minh chúng là số nguyên tố” cho nên bài viết này chỉ quan tâm đến phương pháp sinh số nguyên tố thứ hai. Nếu như toàn bộ các thuật toán sinh số nguyên tố được đưa ra trong các tiêu chuẩn nêu trên chỉ dựa vào “bằng chứng kiểu p-1” thì trong bài này sẽ đưa thêm kiểu “bằng chứng p+1” để thiết kế một thuật toán sinh số nguyên tố chứng minh được với bằng chứng kiểu p± 1. 2. CƠ SỞ TOÁN HỌC 2.1. Một số khái niệm và định lý Định nghĩa 2.1[2]. Biểu diễn NAF (non-adjacent form) của số nguyên dương m, theo công thức sau: m =   1k 0i i i 2m (2.1) với mi  {0,1,1}, mk1  0 và không có hai số hạng cùng dấu liền nhau. Giá trị k được gọi là độ dài của NAF. Định lý 2.1[2]. (i) Với mọi m nguyên dương tồn tại duy nhất NAF và được ký hiệu là NAF(m). (ii) Gọi k là độ dài của NAF(m) thì length(m) + 1≤k (iii) Số các mi khác 0 của NAF(m), ký hiệu là w(NAF(m)), xấp xỉ length(m)/3. - Cho tập ℤN ={0,1,,N1} trên đó xác định hai phép toán cộng và nhân rút gọn theo modulo N. Đặc biệt nếu p là số nguyên tố thì ℤp là một trường. Đặc số của trường là số nguyên dương nhỏ nhất n sao cho: Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 42, 04 - 2016 147 01 1   n i . (2.2) Vành ℤN[x]/(x 2D). Định nghĩa 2.1. Cho đa thức f(ℤN[x]/(x 2D))* ta gọi số nguyên dương nhỏ nhất e sao cho fe mod (N,x2D)ℤN là bậc mở rộng của f theo modulo x 2D và ký hiệu là  fExOrd )Dx,N( 2 . -Phép toán trong (ℤN[x]/(x 2D))* Giả sử đa thức u+vx thuộc (ℤN[x]/(x 2D))*, được ký hiệu là (u,v). Giả sử (u,v), (a,b), (a’,b’)∈ (ℤN[x]/(x 2D))* . Phép nhân tổng quát giữa (a,b) với (a’,b’)(ℤN[x]/(x 2D))* được xác định như sau: (u,v)= (a,b).(a’,b’)= (a+bx).(a’+b’x)= (aa’+ab’x+ba’x+bb’x2). Rút gọn biểu thức (aa’+ab’x+ba’x+ bb’x2) theo modulo x2D, được kết quả như sau: (u,v)= (aa’+bb’D)+(ab’+a’b)x Trong đó các giá trị u và v được rút gọn theo modulo N, theo công thức sau: u = (aa’+bb’D) mod N và v = (ab’+a’b) (mod N) (2.3) Trong trường hợp (u,v) = (a,b)2, khi đó (u,v)= (a,b).(a,b)= (a+bx).(a+bx)= a.a+abx+bax+b2x2, kết quả này sau khi rút gọn theo modulo x2D thu được : a2+b2D+2abx. Khi đó các giá trị u, v được rút gọn theo modulo N theo công thức sau: u = (a2+b2D) mod N và v = (2ab) mod N. (2.4) Trong trường hợp (u,v)= (a,b).(a’,1)= (ax+b).(a’x+1)= aa’x2+ax+ ba’x+b= (ba’+a)x + aa’D+b. Khi đó u, v được xác định qua công thức sau: U=(ba’+a) mod N, v= aa’D+b Mod N (2.5) Ứng dụng biểu diễn NAF để tính (a,b)m ∈(ℤN[x]/(x 2D))* Thuật toán 2.1. (NAF) . Đầu vào: (a,b) ∈(ℤN[x]/(x 2D))*, m là số nguyên dương có NAF(m) =    1k 0i i i 2m . Đầu ra: (u,v) =(a,b) m (mod (N,D)). 1. (u,v) = (1,0); 2. for (k > j  0) {(u,v) ≡ (u,v)2 (mod (N,D)); if (mj==1) (u,v) ≡ (u,v)(a,b) (mod (N,D)); if (mj==1) (u,v) ≡ (u,v)(a,b) (mod (N,D));} 3. return (u,v) Định lý 2.2[1]: N là số nguyên tố lẻ và q là một ước của N-1, a∈ ∗ . Khi đó: ii) Số a thặng dư bậc q theo modul N khi và chỉ khi 1 1   q N a modulo N. ii) Số thặng dư bậc q theo modulo N là Định lý 2.3[1]: Công nghệ thông tin & Khoa học máy tính L.V. Tuấn, B.T. Truyền, “Xây dựng một phương pháp sinh số nguyên tố tất định.” 148 Cho q là số nguyên tố, khi đó mọi số nguyên N trong tập các số dạng N=Aq2+Bq+1 với 0A, B0. Nếu N thoả mãn với hai điều kiện sau: (i) Tìm được a∈ ∗ thỏa mãn 1Na mod N = 1 và gcd( ),1 1 Na q N   =1 (2.6) (ii) B2- 4A là số không chính phương thì n nguyên tố. Định lý 2.4[2]: Cho q là số nguyên tố, khi đó mọi số nguyên N trong tập các số dạng N=Aq2+Bq-1 với 0A, B<q. Nếu N thoả mãn với hai điều kiện sau: (i) Với mỗi D thoả mãn       N D = 1, tìm được a∈ ∗ thỏa mãn u+vx=( + ) ( , − ) ∈ và gcd(v,N)=1 (2.7) (ii) Cả hai giá trị B2+4A và (qB)2+4(A+1) đều không chính phương thì N là số nguyên tố. 2.2. Một số hàm bổ trợ Hàm Random(n) Đầu vào: số tự nhiên n. Đầu ra: số tự nhiên trong khoảng (0,n). Hàm RoundInc(r,a,b) Đầu vào: r, a, b, là các số tự nhiên với a ≤ r ≤ b. Đầu ra: RoundInc(r,a,b) = 1 1 1 a khi r b r khi r b       Hàm SmallFactor(x) Đầu vào: x, số tự nhiên. Đầu ra: Giá trị a, ước nguyên tố không tầm thường nhỏ nhất của x nếu tồn tại với a<216. Bằng 0 trong trường hợp ngược lại. Hàm được thực hiện theo phương pháp chia thử x cho các số tự nhiên từ 2 đến min(216, x   ). Hàm Eratos(k) Đầu vào: k, số tự nhiên thỏa mãn 0<k<33. Đầu ra: p, số nguyên tố ngẫu nhiên k bits. 1. p  2k-1 + Random(2k-1). 2. Trong khi SmallFactor(p)  0 tính p  RoundInc(p,2k-1,2k1). 3. return p. 3. XÂY DỰNG THUẬT TOÁN SINH SỐ NGUYÊN TỐ MỚI Hàm PrimeGen(n) Thuật toán 3.1(Thuật toán sinh số nguyên tố n bít). Đầu vào: n là số nguyên dương là độ dài số nguyên tố cần sinh. Đầu ra: (p,Pwithness), trong đó p là số nguyên tố cần sinh và Pwithness là tập hợp chứa bằng chứng để chứng minh tính nguyên tố của p. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 42, 04 - 2016 149 Giai đoạn chuẩn bị. Tính dãy các số nguyên n[0], n[0], n[1],..., n[k], thoả mãn n[k]= +1 1. k← 0; m← ; bangchung← {}; 2. While (m>32) {2.1. n[k]← 2.2. m← +1 2.3. k← + 1} 3. q←Eratos(n[k]); Pwithness ={}; 4. While(k≥ 0) {4.1. k←k-1; 4.2. t= Random(2); 4.3. (p, bangchung) ←ExtPrimeGen(n[k],q,t). 4.4. q←p; 4.5. Pwithness← Pwithness ∪ bangchung;} 5. Return(p,Pwithness); Hàm ExtPrimeGen(n,q,t) Thuật toán 3.2: Đầu vào: Tham số n là số nguyên dương là độ dài số nguyên tố cần sinh; Tham số q, số nguyên tố thoả mãn n/3<qlen<n-16; Tham số t, kiểu sinh. Đầu ra: (p,bangchung), trong đó p là số nguyên tố với plen =n ; tham số bangchung là bằng chứng để chứng minh tính nguyên tố của vừa sinh p. 1. r0← ; r1← 2. r← Random(r0,r1); 3. p← r*q+(-1)t ; 4. if (t==1) out← CMYTest(p,q) else ) out← PockTest(p.q) 5. While out==”Null” do r←RoundInc(r, r0, r1) p← r*q+(-1)t; If (t==0) out ←CMYTest(p,q) else out ← PockTest(p,q); 6. Return out. Các hàm kiểm tra tính nguyên tố Áp dụng các định lý 2.3 và 2.4 để xây dựng hai hàm kiểm tra tính nguyên tố sau đây: Hàm CMYTest(N,q). Thuật toán 3.3: Đầu vào: Tham số N, số nguyên dương chỉ số nguyên cần cần kiểm tra; Tham số q, số nguyên tố thoả mãn n/3<qlen. Đầu ra:: Bộ 3 tham số (N,a,D), trong trường hợp N là số nguyên tố với Nlen=n; a, D thoả mãn định lý 2.4 về tính nguyên tố của p;“Null” trong trường hợp N là hợp số. 1. Lấy ngẫu nhiên a và D ∈ ∗ sao cho       N D = -1. 2. (u,v)← (a,1)(N+1)/q mod (D,N), nếu gcd(v,N)>1 thì return “Null”; 3. (u,v)← (u,v)q mod (D,N) nếu v≠0, return “Null”; 4. Viết N=Aq2+Bq-1 với 0A,B<q; 5. If (B2+4A) hoặc (q-B)2 +4(A+1) là số chính phương, return “Null”; 6. Return (N,a,D); Hàm PockTest(N,q) Công nghệ thông tin & Khoa học máy tính L.V. Tuấn, B.T. Truyền, “Xây dựng một phương pháp sinh số nguyên tố tất định.” 150 Thuật toán 3.4: Đầu vào: Tham số N, số nguyên dương chỉ số nguyên cần kiểm tra tính nguyên tố; Tham số q, số nguyên tố thoả mãn n/3<qlen. Đầu ra: (N,a), trong trường hợp N là số nguyên tố với Nlen=n. Tham số a thoả mãn điều kiện của định lý 2.3, “Null” trong trường hợp n là hợp số. 1. a← Random(1,N) thỏa aN-1=1 mod N. 2. if gcd(a,N) >1 return “Null” 3. v← a(N-1)/q mod N 4. if (gcd(v-1,N)>1), return “Null” 5. u← vq mod N 6. If u≠1, return “Null” 7. Viết N=Aq2+Bq+1 với 0A,B<q; 8. If (B2-4A) là số chính phương, returrn “Null”. 9. Return (N,a). 4. PHÂN TÍCH THUẬT TOÁN 4.1. Phân tích các bước của thuật toán Trong phần này, chủ yếu tập trung phân tích thuật toán 3.1 (Thuật toán sinh số nguyên tố N bít). Đầu vào của thuật toán là độ dài tính theo đơn vị số bít mà số nguyên tố cần sinh, ký hiệu N. Đầu ra là một cặp (p, Pwithness), trong đó thành phần thứ nhất, ký hiệu p là số nguyên tố sinh được có độ dài n bít; thành phần thứ 2, ký hiệu Pwithness là tập hợp chứa các giá trị là bộ đôi (p,a) đối với kiểu sinh “p-1” hoặc (p,a,D) với kiểu sinh “p+1” ở các vòng lặp khác nhau. Bước 1, 2 của thuật toán tạo ra một mảng có kích cỡ là k. Độ lớn của k phụ thuộc vào độ lớn của n, n[0] ←n, n[1]← +1;...,n[k] ← +1, trong đó n[k]<32. Bước 3, thuật toán tạo ra một số nguyên tố nhỏ hơn 32 bít bằng hàm Eratos. Việc chứng minh hàm Eratos luôn cho ra một số nguyên tố sẽ không trình bày trong bài viết này. Bước 4, Từ số nguyên tố được tạo ra bằng hàm Eratos, vòng lặp thứ nhất hàm ExtprimeGen sẽ tạo ra số nguyên tố p có độ lớn gấp 3 lần số nguyên tố được tạo ra từ hàm Eratos. Vòng lặp thứ 2 hàm ExtprimeGen sẽ tạo ra số nguyên tố p có độ lớn gấp 3 lần số nguyên tố được tạo ra từ vòng lặp thứ nhất... Tính tất định của thuật toán tập trung vào hai hàm CMYTest() và PockTest() được sử dụng trong hàm ExtprimeGen(). Hàm CMYTest sử dụng kết quả nghiên cứu của [Chu Minh Yen] đã được chứng minh là đúng đắn, trong khi đó hàm PockTest() sử dụng hệ quả của định lý Pocklington. Bước 5: Kết thúc vòng lặp While thuật toán tạo ra số nguyên tố p có độ dài n bít. p{x.q+1 r0xr1} }∪ {x.q-1: r0xr1} với r0 và r1 được tính ở bước 1 của thuật toán ExtprimeGen như sau: r0← ; r1← Điều trên có nghĩa số nguyên tố p được sinh ra từ thuật toán 1 luôn có độ dài n bít, tức là 2n1  p  2n1. Kết quả: Thuật toán nếu dừng thì đầu ra của chúng là số nguyên tố n-bits. Nói một cách khác là tính đúng đắn của thuật toán đã được chứng minh. 4.2. Xác suất sai của thuật toán Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 42, 04 - 2016 151 Thuật toán sinh số nguyên tố mà nhóm nghiên cứu xây dựng là thuật toán quyết định, được dựa trên hai thuật toán kiểm tra tính nguyên tố theo hướng “bác bỏ nhầm” [1]. Xác suất sai của thuật toán chính là xác suất bác bỏ nhầm trong hai hàm CMYTest và PockTest. Đối với hàm PockTest(..), với số nguyên tố bất kỳ N = xq+1 với q2N. Nếu giá trị a được chọn trong bước 1 của thuật toán tính hàm PockTest(.,.) là thặng dư bậc q, theo định lý 2.2 thì giá trị v tính được ở bước 3 sẽ thỏa mãn v = 1 (mod N) và do đó gcd(v1,N) =gcd(0, N) =N  1 vì vậy theo điều kiện của bước 4 thì đầu ra của thuật toán sẽ kết luận N là hợp số trong khi N lại là số nguyên tố. Điều trên có nghĩa các số nguyên tố N đã bị hàm PockTest(.,.) kết luận nhầm. Xác suất kết luận nhầm của hàm PockTest(.,.) được gọi là xác suất sai của các thuật toán tương ứng, ký hiệu là Perro(N,q). Hiển nhiên theo công thức xác suất cổ điển ta có Perro1(N,q) = 1 )}(mod1:1{# /)1(    N NaNa qN . Theo định lý 2.2 thì Perro(N,q) = q 1 . (4.1) Xét hàm CMYTest(..), tại bước 2 của thuật toán, trong trường hợp N là số nguyên tố, nhưng mà cấp của phần tử (a,1) là ước của (N+1)/q tức là (u,v) = (a,1)(N+1)/q ≡ (a,0) (mod (N,D) do đó gcd(v,N) =gcd(0,N)= N nên tại bước này của thuật toán cũng cho kết luận nhầm "N là hợp số". Theo [2], xác suất kết luận nhầm một số nguyên tố là hợp số trong CMYTest(..), ký hiệu là Perro2, xác định bởi công thức sau: Perro = q 1 . (4.2) 4.3. Độ phức tạp tính toán Khi xây dựng một thuật toán sinh số nguyên tố trong một tập số R, R⊂N, bao giờ cũng phải có bước lấy phần tử x, xR theo một cách nào đó và kiểm tra tính nguyên tố của x, lặp lại việc lấy theo cách đó cho đến khi x được khẳng định là số nguyên tố theo phép kiểm tra nào đó thì dừng. Tập R đề xuất trong thuật toán trên là tập các số nguyên dương R={x.q+1 r0xr1} }∪ {x.q-1: r0xr1}. Phép kiểm tra tính nguyên tố sử dụng trong thuật toán là hàm CMYTest và PockTest. Thời gian thực hiện thuật toán 1 sẽ tập trung vào thời gian sinh số nguyên tố p có n bít theo hàm ExtprimeGen, mà cốt lõi là thời gian thực hiện hai hàm CMYTest và PockTest, cho nên trong mục này sẽ lần lượt đánh giá thời gian tính của hai hàm trên. Trong [8], các phép cộng, trừ theo modulo có bậc 1, các phép nhân, chia, lấy nghịch đảo có bậc 2 nên khi phân tích độ phức tạp tính toán ở đây ta chỉ xét đến phép nhân theo modulo. Nếu quy ước mỗi phép nhân theo modulo N có thời gian tính là M đơn vị, thì thời gian tính của phép toán nhân các phần tử trong (ℤN[x]/(x 2D))* ở công thức (2.3), (2.4) và (2.5) được xác định trong bổ đề dưới đây: Bổ đề 4.1. (i) Thời gian tính của phép nhân tổng quát trong (ℤN[x]/(x 2D))* là 5M. (ii) Thời gian tính của phép nhân các phần từ trong (ℤN[x]/(x 2D))* với phần tử (a,1) là 3M. (iii)Thời gian tính của phép bình phương tổng quát các phần tử trong (ℤN[x]/(x 2D))* là 4M. Công nghệ thông tin & Khoa học máy tính L.V. Tuấn, B.T. Truyền, “Xây dựng một phương pháp sinh số nguyên tố tất định.” 152 Việc chứng minh bổ đề 4.1 là hiển nhiên khi ta đếm số phép nhân theo modulo N trong các công thức (2.3), (2.4) và (2.5). Bổ đề 4.2. Thời gian tính (a,1)(n+1)/q và (a,1)n+1, ký hiệu là T, được xác định theo biểu thức sau T  (5length(n+1)+ 3 2 length(q)+13)M. (4.3) Chứng minh Tại bước 2 của thuật toán (3.3) ta cần tính (a,1)(N+1)/q mod (N,D). Theo (iii) của định lý 2.1 thì để tính (a,1)(N+1)/q mod (N,D) cần cùng lắm là length((N+1)/q)+1 phép bình phương và 3 1 length((N+1)/q) phép nhân với phần tử (a,1) hoặc (a,1). Do đó thời gian tính giá trị nêu trên là (4(length((N+1)/q)+1)+3 3 1 length((N+1)/q))M. (4.4) Ta có (a,1)N+1 = (u,v)q với (u,v) ≡ (a,1)(N+1)/q mod (N,D) cho nên cũng từ (iii) trong định lý 2.1 thì để tính (u,v)q mod (N,D) ta cần cùng lắm là length(q)+1 phép bình phương và 3 1 length(q) phép nhân với phần tử (u,v) hoặc (u,v). Do đó thời gian tính giá trị nêu trên là (4(length(q)+1)+5 3 1 length(q))M. (4.5) Do length((N+1)/q)+length(q)  length((N+1))+1 nên ta có ngay điều cần chứng minh. Áp dụng bổ đề 4.1 và 4.2 để xác định thời gian tính toán của thuật toán 3.3. Trong hàm CMYTest(..) số phép tính cần phải thực hiện nhiều nhất là (a,1)(N+1)/q mod (D,N), và (u,v)← (u,v)q mod (D,N). Tổng thời gian tính trong hàm CMYTest ký hiệu là NewTime1, được xác định bởi công thức sau: NewTime1 = (c+13+5length(N+1)+ 3 2 length(q))M. (4.6) Trong đó c là hằng số, c= c1+c2+c3, với c1 là thời gian thực hiện bước 1; c2 là thời gian tính gcd(v,N); c3 là thời gian kiểm tra tính chính phương theo modulo ở bước 5. Tương tự ta cũng áp dụng định lý 2.1 để xét độ phức tạp tính toán của thuật toán (4.4), thực hiện trong hàm PockTest(..). Số phép tính cần phải thực hiện nhiều nhất trong thuật toán (4.4) là: giá trị thứ nhất b  a(N1)/q (mod N), giá trị thứ 2 gcd(b1,N) và giá trị thứ 3 là bq (mod N). Dễ thấy b= a(N1)/q (mod N), thì bq mod N = a(N1) mod N. Vậy tổng thời gian để tính giá trị thứ nhất và thứ ba chính bằng thời gian tính của giá trị aN1 (mod N). Giả sử n là độ dài tính theo bít của số nguyên cần kiểm tra tính nguyên tố thì thời gian tính tổng cộng của hàm PockTest(..), ký hiệu là NewTime2 ước lượng là: NewTime2 ≅ n 3+n2 (4.7) 4.4. Lực lượng số nguyên tố. Để xác định lực lượng số nguyên tố sinh ra từ thuật toán, dưới đây xét một số công thức xác định mật độ số nguyên tố: Công thức Gauss. Số các số nguyên tố không quá x, ký hiệu là (x)[4], được đánh giá theo công thức sau. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 42, 04 - 2016 153 (x) ≅ xln x . (4.8) Khi x → ∞ Công thức Chebyshev[4]: Cho A,B là số nguyên dương, giả sử rằng mọi x≥3, khi đó luôn có bất đẳng thức sau: ≤ π(x) ≤ (4.9) Công thức D’richlet[4]. Cho A>0 và gcd(A,B)=1. Số các số nguyên tố không quá x trong lớp thặng dư B theo modulo A, ký hiệu là (A,B)(x) được ước lượng như sau (A,B)(x) ≅ )( )( 1 x A   . (4.10) Với (A) là số các số nguyên dương nhỏ hơn A và nguyên tố cùng nhau với A. Bổ đề 4.3. Số các số nguyên tố m-bits trong lớp thặng dư B∈ ∗ theo modulo A, ký hiệu là (A,B)(2 m-1,2m), được tính như sau: (A,B)(2 m-1,2m) ≅           )1m(m 2m 2ln)A( 2 1m (4.11) Chứnh minh (A,B)(2 m-1,2m) ≅ (A,B)(2 m)  (A,B)(2 m-1) =             2ln)1m( 2 2lnm 2 )A( 1 1mm =           )1m(m 2m 2ln)A( 2 1m . Áp dụng bổ đề trên ta có thể tính được mật độ các số nguyên tố n bít có dạng dạng x.q+1 trong khoảng (2n-1, 2n-1) là: (,)(,) = 1 12112 1                qq nn ≅ q n 12  (4.12) Tượng tự việc xác định mật độ các số nguyên tố n bít dạng x.q-1 trong khoảng ( , ) là (,)(,) = 1 12112 1                qq nn ≅ q n 12  (4.13) Từ (4.10) và (4.11) ta sẽ xác định được mật độ số nguyên tố n bít có dạng xq ±1 trong khoảng ( , ) là: (,±), ≅ q n2 (4.14) Vậy lực lượng số nguyên tố được sinh ra từ thuật toán kiểu “bằng chứng” p±1 là lớn hơn gấp hai lần lực lượng số nguyên tố sinh ra từ thuật toán kiểu “bằng chứng” p+1 hoặc bằng chứng p-1. Công nghệ thông tin & Khoa học máy tính L.V. Tuấn, B.T. Truyền, “Xây dựng một phương pháp sinh số nguyên tố tất định.” 154 5. KẾT LUẬN Vấn đề nghiên cứu quan trọng nhất đạt được là đã kết hợp được hai kiểu sinh số nguyên tố, đó là: Sinh số nguyên tố kiểu p-1 và sinh số nguyên tố kiểu tố p+1. Sự kết hợp này đã tạo ra kiểu sinh số nguyên tố mới, còn gọi là kiểu sinh số nguyên tố p±1. Trên cơ sở nghiên cứu sự kết hợp đó, chúng tôi đã xây dựng nên một thuật toán sinh số nguyên tố tất định. Hơn nữa, thuật toán chúng tôi xây dựng không chỉ sinh ra được số nguyên tố n bít mà còn đưa ra “kiểu bằng chứng” về tính nguyên tố của nó. Ngoài ra, thuật toán dễ dàng cài đặt bằng các ngôn ngữ lập trình, do đó có thể sử dụng và phổ cập rộng rãi. Sự kết hợp giữa các kiểu sinh số nguyên tố để xây dựng nên kiểu sinh số nguyên tố mới hiệu quả hơn là một hướng nghiên cứu quan trọng trong việc sinh các số nguyên tố lớn. Trên cơ sở sự kết hợp hai kiểu sinh số nguyên tố ở trên, chúng tôi có thể đề xuất xây dựng được một số thuật toán sinh số nguyên tố tất định khác, hiệu quả hơn trên cơ sở những thuật toán sinh số nguyên tố đã có sẵn xuất phát từ một số thuật toán sinh số nguyên tố đã có. TÀI LIỆU THAM KHẢO [1]. Lều Đức Tân “Số nguyên tố và đa thức nguyên thủy” , Học viện KTMM, Hà nội, 6- 2002 [2]. Chu Minh Yên. “Phép kiểm tra tính nguyên tố kiểu n+1 mới” , Học viện KTMM Hà nội, 8-2011. [3]. Nguyễn Đức Mạnh, Thái Danh Hậu, Trần Duy Lai. “Một thuật toán sinh số nguyên tố tất định”. Tạp chí Nghiên cứu KHKT& CNQS, 2010. [4]. Richard Crandall, Carl Pomerance. “Prime Numbers, A Computational Perspective”, Second Edition, Springer Science + Business Media, Inc, 2005. [5]. X9.31-1998 “Digital Sinatures Using Reversible Publickey Cryptography for the Financial Servicer Industry (rDSA)”, Accredited Standards Commite X9, Inc, American National Standard for Financial Servicer, 1998. [6]. FIPS PUB 186-3, “Digital Sinature Standrd (DSS)”, 2009. [7]. NIST SP 800-57, “Recommendation for the Key management- Part 1: General (revised)”, 2007. [8]. Dolanld E. Knuth. “The Art of Computer Progamming”. Second edition 1969. Addison-Wesley publish company. ABSTRACT BUILDING AN METHOD FOR DETERMINISTIC PRIME GENERATION In this paper, we have given a general algorithm for deterministic prime generation. This algorithm is based on some algorithms of generation primes which has existed. It is important that the new algorithm allowed to creat the amount of prime number more than the previous algorith and this new algorithm also have given own primeness’ type of proof. Keywords: Public Key Encryption (PKE), Digital signature. Nhận bài ngày 20 tháng 01 năm 2016 Hoàn thiện ngày 27 tháng 02 năm 2016 Chấp nhận đăng ngày 20 tháng 4 năm 2016 Địa chỉ: 1 Học viện Khoa học quân sự; 2 Học viện Kỹ thuật quân sự. * Email: levantuan71@yahoo.com