Số nguyên tố
Phương pháp tính > Kiểm tra tính nguyên tố và chứng minh tính nguyên tố

Một số thuật toán hiện đại nhanh nhất để giải quyết bài toán về tính nguyên tố của một số  n bất kỳ cho trước là các thuật toán xác suất (Monte Carlo), nghĩa là nó có một khả năng nhỏ ngẫu nhiên cho câu trả lời sai. Chẳng hạn, kiểm tra Solovay–Strassen với một số cho trước  p chọn ngẫu nhiên một số  a trong khoảng từ 2 đến  p-2 và sử dụng lũy thừa mô đun để kiểm tra xem  a^{(p-1)/2}\pm 1 có chia hết được bởi  p hay không. Nếu đúng là như vậy thì nó trả lời "có" và ngược lại thì nó trả lời "không". Nếu  p đúng là số nguyên tố thì nó luôn trả lời "có", nhưng nếu  p là hợp số thì nó trả lời "có" với xác suất lớn nhất là 1/2 và "không" với xác suất nhỏ nhất là 1/2. Nếu thuật toán này được lặp lại  n lần trong cùng một số, xác suất lớn nhất để một hợp số vượt qua được thuật toán mọi lần là  1/2^{n}. Vì xác suất đó giảm dần theo cấp số nhân khi số lần thực hiện kiểm tra tăng dần nên nó dẫn đến khả năng cao (nhưng không chắc chắn) rằng một số vượt qua được thuật toán lặp lại đó là số nguyên tố. Mặt khác, nếu một số không vượt qua được kiểm tra thì nó chắc chắn là hợp số. Một hợp số vượt qua được một kiểm tra như thế được gọi là số giả nguyên tố.
Ngược lại, một số thuật toán khác đảm bảo rằng câu trả lời luôn luôn đúng: số nguyên tố sẽ luôn luôn được xác định là số nguyên tố và hợp số sẽ luôn luôn được xác định là hợp số. Chẳng hạn, phát biểu này là đúng đối với giải thuật chia thử. Những thuật toán với đầu ra đảm bảo chính xác bao gồm thuật toán tất định như phép kiểm tra tính nguyên tố AKS, và các thuật toán Las Vegas ngẫu nhiên mà trong đó những lựa chọn ngẫu nhiên của thuật toán không ảnh hưởng gì đến kết quả cuối cùng, chẳng hạn như một số dạng của phép chứng minh tính nguyên tố bằng đường cong elliptic. Khi phương pháp đường cong elliptic kết luận rằng một số là số nguyên tố, nó cũng xuất ra một chứng nhận tính nguyên tố có thể được xác nhận nhanh chóng. Kỹ thuật đường cong elliptic là nhanh nhất trong số các thuật toán với độ chính xác tuyệt đối, nhưng thời gian thực thi chỉ được đo dựa trên thực nghiệm thay vì lập luận chứng minh. Kiểm tra AKS có độ phức tạp tính toán được chứng minh bằng lập luận toán học nhưng hoạt động chậm hơn so với kỹ thuật đường cong elliptic. Các phương pháp này có thể được dùng để tạo ra các số nguyên tố lớn bằng cách tạo và kiểm tra các số ngẫu nhiên đến khi tìm được một số nguyên tố; khi đó, một thuật toán kiểm tra xác suất có thể nhanh chóng loại đi phần lớn hợp số trước khi một thuật toán "chắc chắn đúng" được dùng để xác thực lại rằng các số còn lại là số nguyên tố.
Bảng dưới đây liệt kê một số thuật toán như vậy. Thời gian hoạt động được cho theo số được kiểm tra  n và số vòng lặp  k (đối với thuật toán xác suất). Đồng thời,  \varepsilon  là một số dương nhỏ bất kỳ và  \log  là logarit cơ số không xác định. Ký hiệu O lớn nghĩa là mỗi khoảng thời gian phải được nhân lên bởi một hằng số tỉ lệ để chuyển nó từ một đại lượng vô hướng sang đơn vị thời gian; hằng số này phụ thuộc vào thông số kỹ thuật chẳng hạn như loại máy tính được dùng để thực hiện thuật toán, nhưng không phụ thuộc vào tham số đầu vào  n và  k.
| Thuật toán | Năm phát triển | Dạng | Độ phức tạp thời gian | Ghi chú | Chú thích |
| --- | --- | --- | --- | --- | --- |
| Kiểm tra AKS | 2002 | tất định |  O((\log n)^{6+\varepsilon }) |  |  |
| Chứng minh đường cong elliptic | 1986 | Las Vegas |  O((\log n)^{4+\varepsilon }) (theo thực nghiệm) |  |  |
| Kiểm tra Baillie–PSW | 1980 | Monte Carlo |  O((\log n)^{2+\varepsilon }) |  |  |
| Kiểm tra Miller–Rabin | 1980 | Monte Carlo |  O(k(\log n)^{2+\varepsilon }) | xác suất sai số  4^{-k} |  |
| Kiểm tra Solovay–Strassen | 1977 | Monte Carlo |  O(k(\log n)^{2+\varepsilon }) | xác suất sai số  2^{-k} |  |