Tên của một sự tiếp nối hấp dẫn khác của bài kiểm tra tính nguyên tố Fermat là gì?
Một ví dụ đơn giản đặc biệt của một bài kiểm tra xác suất là bài kiểm tra tính nguyên tố Fermat, dựa trên thực tế (định lý nhỏ của Fermat) rằng np≡n (mod p) cho bất kỳ n nào nếu p là một số nguyên tố. Nếu chúng ta có một số b mà chúng ta muốn kiểm tra tính nguyên tố, thì chúng ta sẽ tìm ra nb (mod b) cho một giá trị ngẫu nhiên của n làm bài kiểm tra của chúng ta. Một lỗ hổng với bài kiểm tra này là có một số số hợp số (số Carmichael) thoả mãn đồng nhất thức Fermat mặc dù chúng không phải là số nguyên tố, vì vậy bài kiểm tra không có cách nào phân biệt giữa số nguyên tố và số Carmichael. Tuy nhiên, số Carmichael hiếm hơn đáng kể so với số nguyên tố, vì vậy bài kiểm tra này có thể hữu ích cho mục đích thực tế. Các phần mở rộng mạnh mẽ hơn của bài kiểm tra tính nguyên tố Fermat, chẳng hạn như các bài kiểm tra Baillie-PSW, Miller-Rabin và Solovay-Strassen, được đảm bảo sẽ thất bại ít nhất một thời gian khi áp dụng cho một số hợp số.
Xét nghiệm Solovay-Strassen