Kiểm tra tính nguyên tố

Kiểm tra tính nguyên tố (tiếng Anh: "primality test") là bài toán kiểm tra xem một số tự nhiên formula_1 có phải là số nguyên tố hay không. Bài toán này đặc biệt trở nên quan trọng khi các hệ mật mã khoá công khai ra đời.
Các phương pháp thô sơ.
Phương pháp đơn giản nhất để kiểm tra một số formula_1 có là số nguyên tố không là kiểm tra xem nó có chia hết cho các số formula_3 nằm trong khoảng 2 đến formula_4 hay không. Nếu formula_1 chia hết cho một số formula_3 nào đó thì formula_1 là hợp số (composite), ngược lại formula_1 là số nguyên tố.
Thực ra việc kiểm tra với formula_3 từ 2 đến formula_4 là không cần thiết, mà chỉ cần kiểm tra đến formula_11. Đó là vì nếu formula_1 là hợp số thì nó chắc chắn có ước số không vượt quá formula_11.
Chúng ta cũng có thể bỏ qua việc kiểm tra trường hợp formula_14 bằng cách chỉ xét các số lẻ. Đi xa hơn một chút, ta chỉ cần xét các số dạng formula_15 và bỏ qua việc kiểm tra 2 trường hợp formula_14 và formula_17. Đó là vì tất cả các số nguyên tố đều có dạng formula_18 với formula_19 nào đó và formula_20; mà trong đó formula_21, formula_22, formula_23 chia hết cho 2, còn formula_24 thì chia hết cho 3. Tiếp tục với các nhận xét đó, ta có thể tổng quát hóa thành thuật toán sàng Eratosthenes.
Kiểm tra theo xác suất.
Các phép kiểm tra tính nguyên tố hay dùng nhất là các thuật toán ngẫu nhiên. Giả sử có một mệnh đề Q(p,a) nào đó đúng với mọi số nguyên tố "p" và một số tự nhiên "a" &lt;= "p". Nếu "n" là một số tự nhiên lẻ và mệnh đề Q(n,a) đúng với một "a"&lt;= "n" được lấy ngẫu nhiên, khi đó "a" "có khả năng" là một số nguyên tố. Ta đưa ra một thuật toán, kết luận rằng "n" là số nguyên tố. Nó là một thuật toán ngẫu nhiên hay thuật toán xác suất. Trong các thuật toán loại này, dùng một kiểm tra ngẫu nhiên không bao giờ kết luận một số nguyên tố là hợp số nhưng có thể kết luận một hợp số là số nguyên tố. Xác suất sai của phép kiểm tra có thể giảm xuống nhờ việc chọn một dãy độc lập các số "a"; nếu với mỗi số "a" xác suất để thuật toán kết luận một hợp số là số nguyên tố là nhỏ hơn một nửa thì sau "k" lần thử độc lập, xác suất sai là nhỏ hơn 2−k, độ tin cậy của thuật toán sẽ tăng lên theo "k".
Cấu trúc cơ bản của một phép kiểm tra ngẫu nhiên là:
Sau một loạt lần kiểm tra, nếu không tìm được bằng chứng chứng tỏ "n" là hợp số thì ta kết luận "n" là số nguyên tố.
Các phép kiểm tra tính nguyên tố ngẫu nhiên là
Các phép kiểm tra tất định.
Vào năm 2002, Manindra Agrawal, Nitin Saxena và Neeraj Kayal đề xuất một giải thuật tất định kiểm tra tính nguyên tố, là kiểm tra AKS, có khả năng chạy trong O((log "n")12). Trên thực tế thuật toán này chạy chậm hơn các phương pháp xác suất.
Độ phức tạp.
Trong lý thuyết độ phức tạp, bài toán về tính nguyên tố được gọi đơn giản là bài toán nguyên tố. Dễ thấy rằng nó là coNP: bài toán ngược của nó, bài toán hợp số là NP.
Năm 1975, Vaughan Pratt nhận thấy rằng tồn tại các thuật toán kiểm tra tính nguyên tố trong thời gian đa thức, và như vậy PRIMES là NP, và do đó thuộc về NP ∩ coNP.
Vào năm 2002, Manindra Agrawal, Nitin Saxena và Neeraj Kayal đề xuất một giải thuật tất định kiểm tra tính nguyên tố, là kiểm tra AKS, có khả năng chạy trong O((log n)12). Thế cho nên PRIMES là P.
Các phương pháp lý thuyết số.
Có một vài phương pháp khác trong lý thuyết số để kiểm tra tính nguyên tố như kiểm tra Lucas-Lehmer và kiểm tra Proth. Chúng thường dựa vào việc phân tích "n" + 1, "n" − 1, hoặc những số khác. Tuy nhiên các phương pháp này không dừng cho các số tự nhiên "n" bất kỳ mã chỉ cho các số có một dạng đặc biệt nào đó
Kiểm tra Lucas-Lehmer dựa trên tính chất: bậc ("multiplicative order") của một số "a" modulo "n" là "n" − 1 với "n" là số nguyên tố và "a" là căn nguyên thủy ("primitive root") modulo n. Nếu ta có thể biểu diễn "a" chỉ theo "n", ta có thể thấy "n" là nguyên tố.