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

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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 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 | sửa mã nguồn]

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

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

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

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 | sửa mã nguồn]

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 | sửa mã nguồn]

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 | sửa mã nguồn]

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 thuỷ (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ố.

Kiểm tra tính chất nguyên tố[sửa | sửa mã nguồn]

Số nguyên tố là số chỉ chia hết cho 1 và chính nó, nghĩa là Số nguyên tố chia cho tích các ước số của chính nó phải bằng 1 (Tính chất nguyên tố- ký hiệu T).

Ví dụ: 3 là số nguyên tố thì 3 chia cho tích các ước số của 3 = 1.

4 không phải là số nguyên tố thì 4 chia cho tích các ước số của 4 = 1/2.

Vậy muốn biết một số có phải là Số nguyên tố không ta chỉ việc: Lấy số đó nhân với Tính Chất nguyên tố của chính nó, nếu kết quả vẫn là chính nó thì nó là số nguyên tố(Định lý Chiến Thắng số nguyên tố - phần chứng minh)

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]