Тест простоты

---

Вопрос определения того, является ли натуральное число ${\displaystyle N}$ простым, известен как проблема простоты.

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

Проблемы дискретной математики являются одними из самых математически сложных. Одна из них — задача факторизации, заключающаяся в поиске разложения числа на простые множители. Для её решения необходимо найти простые числа, что приводит к проблеме простоты. Задача теста простоты относится к классу сложности P, то есть время работы алгоритмов её решения зависит от размера входных данных полиномиально, что было доказано в 2002 году. Существует аналогичное, однако недоказанное, утверждение для задачи факторизации.

Некоторые приложения математики с использованием факторизации требуют ряда очень больших простых чисел, выбранных случайным образом. Алгоритм их получения, основанный на постулате Бертрана:

Время решения задачи этим алгоритмом не определено, но есть большая вероятность, что оно всегда является полиномиальным, пока имеется достаточно простых чисел, и они распределены более-менее равномерно. Для простых случайных чисел эти условия выполняются.

---