Kiểm tra nguyên tố Miller-Rabin kết hợp kiểm tra Fermat và kiểm tra căn bậc hai Fermat theo phương pháp kinh điển để tìm giả nguyên tố mạnh (strong pseudoprime). Trong kiểm tra này, viết n-1 như tích số lẻ m và lũy thừa 2:
n-1 = m × 2ᵏ
Kiểm tra Fermat cơ sở a viết:
aⁿ⁻¹ = aᵐˣ²ᵏ = [aᵐ]²ᵏ = [aᵐ]²ˣ²ˣ...ˣ² (k lần)
Nói cách khác, thay vì tính aⁿ⁻¹ (mod n) một bước, làm trong k+1 bước. Lợi ích k+1 bước: mỗi bước kiểm tra căn bậc hai có thể thực hiện. Nếu kiểm tra căn thất bại, dừng và tuyên bố n hợp số.
Mỗi bước, đảm bảo kiểm tra Fermat qua và kiểm tra căn bậc hai thỏa mãn giữa tất cả cặp bước liền kề (nếu kết quả 1).
Khởi tạo
Chọn cơ sở a và tính T = aᵐ, trong đó m = (n-1)/2ᵏ
Nếu T = +1 hoặc -1 tuyên bố n là giả nguyên tố mạnh và dừng. Vì nếu T = ±1, T thành 1 bước sau và giữ 1 cho đến qua kiểm tra Fermat. Hơn nữa, T qua kiểm tra căn vì T = 1 bước sau và căn 1 (bước sau) là ±1.
Nếu T là giá trị khác, không chắc n nguyên tố hay hợp số, tiếp bước sau.
Bước 1: Bình phương T
Nếu kết quả +1, chắc chắn Fermat qua vì T giữ 1 cho các kiểm tra sau. Kiểm tra căn không qua. Vì T=1 bước này và khác ±1 bước trước, tuyên bố n hợp số và dừng.
Nếu kết quả -1, biết n cuối cùng qua Fermat. Cũng biết qua kiểm tra căn vì T=-1 bước này và thành 1 bước sau. Tuyên bố n giả nguyên tố mạnh và dừng.
Nếu T giá trị khác, không chắc có nguyên tố hay không. Tiếp bước sau.
Bước 2 đến Bước K-1:
Bước này và các bước tiếp theo tiếp tục từ bước 2 đến K-1 giống bước 1.
Bước K:
Bước này không cần. Nếu đến bước này chưa quyết định, bước này không giúp. Nếu kết quả 1, Fermat qua, nhưng vì kết quả bước trước không ±1, kiểm tra căn không qua. Sau bước k-1, nếu chưa dừng, tuyên bố n hợp số. Miller-Rabin cần từ bước 0 đến K-1.