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ó. | 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 ], [FIP ], [TCVN 7635; 2007], [ISO/IEC 18032;2004], 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 . Một số khái niệm và định lý Định nghĩa [2]. Biểu diễn
