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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Тест простоты — алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты.

Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только в 2002 году было доказано, что она полиномиально разрешима. Тем не менее, тестирование простоты значительно легче факторизации заданного числа.

Общие тесты простоты[править | править вики-текст]

Специализированные тесты простоты[править | править вики-текст]

См. также[править | править вики-текст]

Литература[править | править вики-текст]