Phép kiểm tra tính nguyên tố AKS

Phép kiểm tra tính nguyên tố AKS (còn được gọi là phép kiểm tra tính nguyên tố Agrawal–Kayal–Saxena và phép kiểm tra cyclotomic AKS) là một thuật toán chứng minh tính nguyên tố xác định được được phát triển và công khai bởi Manindra Agrawal, Neeraj Kayal, và Nitin Saxena, là các nhà khoa học máy tính tại Viện công nghệ Ấn Độ Kanpur vào 06-08-2002, trong bài báo khoa học có tựa đề "PRIMES is in P". Đây là thuật toán đầu tiên dùng để xác định một số bất kỳ là số nguyên tố hay hợp số trong một thời gian dạng đa thức. Các tác giả của thuật toán này được nhận Giải thưởng Gödel năm 2006 và Giải thưởng Fulkerson năm 2006.

Tầm quan trọng[sửa | sửa mã nguồn]

AKS là thuật toán chứng minh tính nguyên tố đầu tiên đồng thời thỏa mãn 4 tính chất: tính tổng quát, tính đa thức, tính xác định, và tính vô điều kiện. Các thuật toán cũ trước đây được phát triển trong nhiều thế kỷ và thỏa mãn 3 tính chất nêu trên, nhưng không đồng thời thỏa mãn cả 4 tính chất.

Thuật toán AKS có thể được sử dụng để xác minh tính nguyên tố của bất kỳ số tổng quát. Nhiều thuật toán kiểm tra tính nguyên tố chỉ có thể áp dụng với số cho trước thỏa các điều kiện nhất định. Ví dụ, Thuật toán Lucas–Lehmer chỉ áp dụng cho các số nguyên tố Mersenne, trong khi Thuật toán Pépin chỉ được áp dụng cho số Fermat.
Thời gian chạy tối đa của thuật toán có thể được biễu diễn bằng một đa thức mà không phải là số chữ số. Thuật toán ECPP và APR có thể chứng minh hay bác bỏ tính nguyên tố của một số nhưng không đảm bảo thời gian chạy có dạng đa thức cho tất cả đầu vào.
Thuật toán AKS đảm bảo một cách xác định nhận ra mục tiêu là số nguyên tố hay là hợp số. Các kiểm tra ngẫu nhiên như Kiểm tra Miller-Rabin và Baillie–PSW, có thể kiểm tra tính nguyên tố trong thời gian đa thức, nhưng kết quả chỉ là một xác suất.
Tính đúng đắn của thuật toán AKS là không phụ thuộc vào bất kỳ giả thuyết con chưa được chứng minh nào. Ngược lại, phiên bản Miller của Kiểm tra Miller-Rabin là hoàn toàn xác định và chạy trong thời gian đa thức cho tất cả đầu vào, nhưng tính đúng đắn của nó phụ thuộc vào tính đúng của giả thuyết chưa được chứng minh, Giả thuyết Riemann Tổng quát.

Mặc dù thuật toán có tầm quan trọng lý thuyết to lớn, nó không được sử dụng trong thực tế. Đối với đầu vào 64-bit, kiểm tra tính nguyên tố Baillie-PSW là có tính xác định và chạy nhanh hơn. Đối với đầu vào lớn hơn, hiệu suất của các phép thử (có tính đúng đắn vô điều kiện) ECPP và APR cao hơn nhiều so với thuật toán AKS.