Kiểm tra Miller-Rabin là một thuật toán xác suất để kiểm tra tính nguyên tố cũng như các thuật toán kiểm tra tính nguyên tố: Kiểm tra Fermat và Kiểm tra Solovay-Strassen. Nó được đề xuất đầu tiên bởi Gary L. Miller như một thuật toán tất định, dựa trên giả thiết Riemann tổng quát; Michael O. Rabin đã sửa chữa nó thành một thuật toán xác suất.Khi sử dụng kiểm tra Miller-Rabin chúng ta căn cứ vào một mệnh đề Q(p, a) đúng với các số nguyên tố p và mọi số tự nhiên a ∈ A ⊂ N {\displaystyle a\in A\subset \mathbb {N} } và kiểm tra xem chúng có đúng với số n muốn kiểm tra và một số a ∈ A {\displaystyle a\in A} được chọn ngẫu nhiên hay không. Nếu mệnh đề Q(n, a) không đúng, tất yếu n không phải là số nguyên tố, còn nếu Q(n, a) đúng, số n có thể là số nguyên tố với một xác suất nào đó. Khi tăng số lần thử, xác suất để n là số nguyên tố tăng lên.