Тест простоты
Материал из Википедии — свободной энциклопедии
 |
Это незавершённая статья. Вы поможете проекту, исправив и дополнив её. Это примечание следует заменить более точным. |
Тест простоты — алгоритм, который по заданному натуральному числу определяет является ли это число простым. Различают детерминированные и вероятностные тесты.
Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только в 2002 году было доказано, что она полиномиально разрешима. Тем не менее, тестирование простоты значительно легче факторизации заданного числа.
