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

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