Một Số nguyên tố là một số tự nhiên lớn hơn 1 không thể viết dưới dạng tích của hai số nhỏ hơn nó. Số tự nhiên lớn hơn 1 và không phải số nguyên tố được gọi là hợp số. Ví dụ 5 là số nguyên tố vì nó không thể viết ở dạng tích, 1 × 5 hay 5 × 1 đều là chính nó. Tuy nhiên, 6 là hợp số vì nó có thể viết dưới dạng tích của hai số khác ``(2 × 3)` và đều nhỏ hơn 6.
Kiểm tra nguyên hàm là một thuật toán để xác định xem một số được cho có phải là số nguyên tố hay không. Nó cũng được sử dụng cho lĩnh vực mật mã học. Không giống như phân tích thừa số, kiểm tra nguyên hàm thường không đưa ra thừa số nguyên tố, mà chỉ cho biết số đầu vào có phải là số nguyên tố hay không. Thừa số hóa được cho là một vấn đề khó về mặt tính toán, trong khi kiểm tra nguyên hàm tương đối dễ dàng (thời gian chạy của nó là đa thức với cùng kích thước của đầu vào).