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 ${\displaystyle n}$ 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ố ${\displaystyle n}$ có là số nguyên tố không là kiểm tra xem nó có chia hết cho các số ${\displaystyle m}$ nằm trong khoảng 2 đến ${\displaystyle n-1}$ hay không. Nếu ${\displaystyle n}$ chia hết cho một số ${\displaystyle m}$ nào đó thì ${\displaystyle n}$ là hợp số (composite), ngược lại ${\displaystyle n}$ là số nguyên tố.

Thực ra việc kiểm tra với ${\displaystyle m}$ từ 2 đến ${\displaystyle n-1}$ là không cần thiết, mà chỉ cần kiểm tra đến ${\displaystyle {\sqrt {n}}}$. Đó là vì nếu ${\displaystyle n}$ là hợp số thì nó chắc chắn có ước số không vượt quá ${\displaystyle {\sqrt {n}}}$.

Chúng ta cũng có thể bỏ qua việc kiểm tra trường hợp ${\displaystyle m=2}$ 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 ${\displaystyle 6k\pm 1}$ và bỏ qua việc kiểm tra 2 trường hợp ${\displaystyle m=2}$ và ${\displaystyle m=3}$. Đó là vì tất cả các số nguyên tố đều có dạng ${\displaystyle 6k+i}$ với ${\displaystyle k}$ nào đó và ${\displaystyle i=0,\pm 1,\pm 2}$; mà trong đó ${\displaystyle 6k+0}$, ${\displaystyle 6k+2}$, ${\displaystyle 6k+4}$ chia hết cho 2, còn ${\displaystyle 6k+3}$ 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 <= p. Nếu n là một số tự nhiên lẻ và mệnh đề Q(n,a) đúng với một a<= 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à:

1. Chọn một số ngẫu nhiên a.
2. Kiểm tra một hệ thức nào đó giữa số a và số n đã cho. Nếu hệ thức sai thì chắc chắn n là một hợp số (số a là "bằng chứng" chứng tỏ n là hợp số) và dừng thuật toán.
3. Lặp lại bước 1 cho đến khi đạt được số lần đã định hoặc gặp bước 2.

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à

Phép kiểm tra tính nguyên tố của Fermat (kiểm tra Fermat. Đây là phép thử heuristic; tuy nhiên ít người sử dung phép thử này

Được sử dụng nhiều hơn là Kiểm tra Miller-Rabin và Kiểm tra Solovay-Strassen. Với mỗi hợp số n, ít nhất 3/4 (với kiểm tra Miller-Rabin) hoặc 1/2 (Với kiểm tra Solovay-Strassen) các số a là bằng chứng chứng tỏ n là hợp số).

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)¹²). 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)¹²). 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ố.

Xem thêm

• Số nguyên tố

Chú thích

Tham khảo