Kiểm tra nguyên tố là thuật toán quyết định số đầu vào có phải nguyên tố. Một số kiểm tra xác định (deterministic) luôn đúng quyết định số nguyên tố hoặc hợp số.
Kiểm tra xác định nhanh nhất được phát minh 2004. Ba nhà khoa học máy tính: Agrawal, Kayal, Saxena phát minh AKS chạy trong O~(log(n)⁶) thời gian, O~(f(n)) = O(f(n)·log(f(n))ᵏ) với k nguyên. Tuy đột phá, tốc độ này khá chậm so với yêu cầu an toàn thông tin.
Lợi ích số nguyên tố: dùng trong mật mã học. Hệ mật mã tiêu chuẩn RSA cần số nguyên tố làm khóa thường >1024-bit cho bảo mật cao.
Xử lý số lớn như vậy, phương pháp sau không tốt. Không dễ làm việc số lớn đặc biệt khi phép toán / và % trong kiểm tra nguyên tố.
Do đó, thuật toán kiểm tra nguyên tố tốt nhất chỉ quyết định số cho là "nguyên tố có xác suất" (probable prime) hoặc hợp số.
Có các loại kiểm tra nguyên tố:
Thuật toán xác định (Deterministic Algorithm) - Chấp nhận số nguyên và luôn xuất ra nguyên tố hoặc hợp số. Luôn cho câu trả lời đúng.
Thuật toán chia hết (Divisibility Algorithm) - Kiểm tra nguyên tố đơn giản nhất: cho số n, kiểm tra số nguyên 2 đến n-1 có chia hết n. Nếu n chia hết m, n hợp số ngược lại nguyên tố. Tuy nhiên, thay vì test tất cả m đến n-1, chỉ cần test m đến √n. Nếu n hợp số thì phân tích thành 2 giá trị, ít nhất một ≤ √n.
Thuật toán xác suất (Probabilistic Algorithm) - Cho câu trả lời đúng hầu hết thời gian, không phải mọi lúc. Kiểm tra n có thỏa điều kiện tất cả nguyên tố phải thỏa. Trả về nguyên tố/hợp số theo quy tắc:
Nếu số test thực sự nguyên tố, thuật toán chắc chắn trả nguyên tố.
Nếu số test thực sự hợp số, trả hợp số với xác suất 1-ε, nhưng có thể trả nguyên tố với xác suất ε. Xác suất sai giảm nếu chạy thuật toán 'm' lần, lỗi giảm thành εᵐ.
Kiểm tra nguyên tố Fermat - Từ Định lý Fermat nhỏ: nếu n nguyên tố, aⁿ⁻¹ ≡ 1 (mod n). Cho n và a