Khi sử dụng một thuật toán xác suất, làm thế nào là xác suất mà số được tổng hợp thể hiện bằng toán học?
Các bài kiểm tra tính nguyên tố hiện đại cho các số chung n có thể được chia thành hai lớp chính, xác suất (hoặc "Monte Carlo") và các thuật toán xác định. Các thuật toán xác định cung cấp một cách để biết chắc chắn liệu một số nhất định có phải là số nguyên tố hay không. Ví dụ, phân chia thử nghiệm là một thuật toán xác định bởi vì, nếu được thực hiện chính xác, nó sẽ luôn xác định một số nguyên tố là số nguyên tố và một số tổng hợp là tổng hợp. Các thuật toán xác suất thường nhanh hơn, nhưng không hoàn toàn chứng minh rằng một số là số nguyên tố. Các bài kiểm tra này dựa vào việc kiểm tra một số nhất định một cách ngẫu nhiên một phần. Ví dụ, một bài kiểm tra nhất định có thể vượt qua tất cả thời gian nếu áp dụng cho một số nguyên tố, nhưng chỉ vượt qua với xác suất p nếu áp dụng cho một số tổng hợp. Nếu chúng ta lặp lại bài kiểm tra n lần và vượt qua mọi lúc, thì xác suất mà số của chúng ta là tổng hợp là 1/(1-p)n, giảm theo cấp số nhân với số lượng các bài kiểm tra, vì vậy chúng ta có thể chắc chắn như chúng ta muốn (mặc dù không bao giờ hoàn toàn chắc chắn) rằng số là số nguyên tố. Mặt khác, nếu thử nghiệm bao giờ thất bại, thì chúng ta biết rằng số là tổng hợp.
1/(1-p)n