Вопрос определения того, является ли натуральное число
N
{\displaystyle N}
простым, известен как проблема простоты.
Тестом простоты (или проверкой простоты) называется алгоритм, который, приняв на входе число
N
{\displaystyle N}
, позволяет либо не подтвердить предположение о том, является ли это число составным, либо точно утверждать его простоту. Во втором случае он называется истинным тестом простоты.
Таким образом, тест простоты представляет собой только гипотезу о том, что если алгоритм не подтвердил предположение о составности числа
N
{\displaystyle N}
, то это число может являться простым с определённой вероятностью. Это определение подразумевает меньшую уверенность в соответствии результата проверки истинному положению вещей, нежели истинное испытание на простоту, которое даёт математически подтверждённый результат.