Số 8 546 289 127 có phải là số nguyên tố không?
Muốn biết một số có phải là số nguyên tố hay không thì sàng Eratosthenes nhanh chóng cho thấy bị hạn chế: những tính toán mà nó quy định nhanh chóng trở nên quá dài. Năm 1976, Gary Miller, ở Trường đại học Califomia, và Michael Rabin, ở Viện Công nghệ Massachusetts (MIT), đã nghĩ ra một phép thử giúp biết nhanh chóng một số có phải là số nguyên tố hay không nhưng hơi không chắc chắn. Khi phép thử cho biết số đó không phải là số nguyên tố, thì người ta có thể tin cậy; nhưng khi nó chỉ ra điều ngược lại, thì có một xác suất sao, mặc dù xác suất này cực nhỏ. Ngoài ra, trong các ứng dụng với số nguyên tố (như ghi mật mã), những số không phải là số nguyên tố vượt qua phép Miller-Rabin ít nhiều có thể sử dụng được như đã từng sử dụng, trong chừng mực mà không ai có khả năng tìm thấy số chia/ước số của chúng. Năm 2002, Manindra Agrawal, Neeraj Kayal và Nitin Saxena, ở Vện Công nghệ Kampur, đã gây ấn tượng mạnh khi trình bày một phương pháp chắc chắn đến 100% và có thời gian thực hiện không được cho rằng quá nhanh nếu con số phải phân tích càng lớn. Phép thử này rất đơn giản nếu so với khó khăn là lô thông thường của loại bài toán này. Tuy nhiên, phương pháp AKS (chữ đầu tên ghép của ba tác giả) này vẫn không cạnh tranh được với các phép thử hiện có, như phép thử Miller-Rabin. Những cải tiến đang diễn ra có thể giúp AKS tự hạn định.
