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

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ó.
Nội dung trích xuất từ 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 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: k 1 m= m 2 i 0 i i (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: 146 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.” Nghiên cứu khoa học công nghệ n 1  0 . i 1 (2.2) Vành ℤN[x]/(x2D). Định nghĩa 2.1. Cho đa thức f(ℤN[x]/(x2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 x2D và ký hiệu là ExOrd( N,x 2 D) f  . -Phép toán trong (ℤN[x]/(x2D))* Giả sử đa thức u+vx thuộc (ℤN[x]/(x2D))*, được ký hiệu là (u,v). Giả sử (u,v), (a,b), (a’,b’)∈ (ℤN[x]/(x2D))* . Phép nhân tổng quát giữa (a,b) với (a’,b’)(ℤN[x]/(x2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) 2 Trong trường hợp (u,v)= (a,b).(a’,1)= (ax+b).(a’x+1)= aa’x +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]/(x2D))* Thuật toán 2.1. (NAF) . Đầu vào: (a,b) ∈(ℤN[x]/(x2D))*, m là số nguyên dương có k 1 NAF(m) = m 2 i 0 i i . Đầ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 đó: N 1 q ii) Số a thặng dư bậc q theo modul N khi và chỉ khi a  1 modulo N. ii) Số thặng dư bậc q theo modulo N là Định lý 2.3[1]: Tạp chí Nghiên cứu KH&CN quân sự, Số 42, 04 - 2016 147  Công nghệ thông tin & Khoa học máy tính 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: ...