Nhấn vào đây để đọc bằng ngôn ngữ khác: English
Một số nguyên tố (hoặc một số nguyên tố) là một số tự nhiên lớn hơn 1 mà không thể được tạo ra bằng cách nhân hai số tự nhiên nhỏ hơn. Một số tự nhiên lớn hơn 1 mà không phải là số nguyên tố được gọi là số hợp số. Ví dụ, 5 là số nguyên tố vì cách duy nhất để viết nó dưới dạng một tích, 1 × 5 hoặc 5 × 1, đều liên quan đến chính 5. Tuy nhiên, 6 là số hợp vì nó là tích của hai số (2 × 3) mà đều nhỏ hơn 6.
Một thử nghiệm tính nguyên tố là một thuật toán để xác định xem một số đầu vào có phải là số nguyên tố hay không. Giữa các lĩnh vực toán học khác, nó được sử dụng cho mật mã học. Không giống như phân tích thành phần số nguyên, các thử nghiệm tính nguyên tố không cung cấp thông tin về các số nguyên tố, chỉ nói xem số đầu vào có phải là số nguyên tố hay không. Phân tích thành phần được cho là một vấn đề khó tính toán, trong khi kiểm tra tính nguyên tố dễ dàng hơn nhiều (thời gian chạy của nó là đa thức theo kích thước của đầu vào).