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 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ơ sửa

Phương pháp đơn giản nhất để kiểm tra một số   có là số nguyên tố không là kiểm tra xem nó có chia hết cho các số   nằm trong khoảng 2 đến   hay không. Nếu   chia hết cho một số   nào đó thì  hợp số (composite), ngược lại   là số nguyên tố.

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

Chúng ta cũng có thể bỏ qua việc kiểm tra trường hợp   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   và bỏ qua việc kiểm tra 2 trường hợp   . Đó là vì tất cả các số nguyên tố đều có dạng   với   nào đó và  ; mà trong đó  ,  ,   chia hết cho 2, còn   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 sửa

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-RabinKiể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 sửa

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 sửa

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ố sửa

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-Lehmerkiể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 nn − 1 với n là số nguyên tố và acă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ửa

Chú thích sửa

Tham khảo sửa