Tài liệu 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ế, ...
9 trang |
Chia sẻ: quangot475 | Lượt xem: 496 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Xây dựng một phương pháp sinh số nguyên tố tất định, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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}, mk1 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,,N1} 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
2D).
Định nghĩa 2.1. Cho đa thức f(ℤN[x]/(x
2D))* ta gọi số nguyên dương nhỏ nhất e sao
cho fe mod (N,x2D)ℤN là bậc mở rộng của f theo modulo x
2D và ký hiệu là
fExOrd
)Dx,N( 2
.
-Phép toán trong (ℤN[x]/(x
2D))*
Giả sử đa thức u+vx thuộc (ℤN[x]/(x
2D))*, được ký hiệu là (u,v). Giả sử (u,v), (a,b),
(a’,b’)∈ (ℤN[x]/(x
2D))* . Phép nhân tổng quát giữa (a,b) với (a’,b’)(ℤN[x]/(x
2D))*
đượ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 x2D, đượ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 x2D 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
2D))*
Thuật toán 2.1. (NAF) . Đầu vào: (a,b) ∈(ℤN[x]/(x
2D))*, 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
0A, B0. Nếu N thoả mãn với hai điều kiện sau:
(i) Tìm được a∈
∗ thỏa mãn
1Na 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
0A, 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à (qB)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,2k1).
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 0A,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 0A,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 r0xr1} }∪ {x.q-1: r0xr1} 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à
2n1 p 2n1.
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 q2N. 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(v1,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, xR 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 r0xr1} }∪ {x.q-1: r0xr1}. 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
2D))* ở 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
2D))* là 5M.
(ii) Thời gian tính của phép nhân các phần từ trong (ℤN[x]/(x
2D))* 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
2D))* 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(N1)/q (mod N), giá trị thứ 2 gcd(b1,N) và giá trị thứ 3
là bq (mod N). Dễ thấy b= a(N1)/q (mod N), thì bq mod N = a(N1) 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ị aN1 (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
Các file đính kèm theo tài liệu này:
- 19_levantuan_1983_2150045.pdf