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

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

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

Общие тесты простоты

• Перебор делителей
• Теорема Вильсона
• Тест Ферма (основан на малой теореме Ферма)
• Тест Миллера
• Тест Миллера — Рабина, вероятностный тест, широко применяемый на практике
• Тест Соловея — Штрассена
• Тест простоты Люка
• Тест Агравала — Каяла — Саксены (Тест AKS), первый полиномиальный детерминированный тест простоты
• Тест BPSW (англ.), вероятностный тест
• ECPP (англ.), Elliptic curve primality proving - детерминированный тест
• APRT+CL (англ.), - детерминированный тест простоты Адлемана-Померанса-Румели, усовершенствованный Коэном (англ.) и Ленстрой.

Специализированные тесты простоты

• Тест Люка — Лемера для чисел Мерсенна
• Тест Пепина для чисел Ферма
• Тест Люка — Лемера — Ризеля (англ.) для чисел Ризеля
• Теорема Прота для чисел Прота

Литература

• Василенко О. Н. Глава 1. Тестирование чисел на простоту и построение больших простых чисел // Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — С. 12—56. — 328 с. — ISBN 5-94057-103-4
• Нестеренко Ю. В. Глава 4.6. Как проверить большое число на простоту // Введение в криптографию / Под ред. В. В. Ященко. — Питер, 2001. — 288 с. — ISBN 5-318-00443-1
• Шнайер Б. Часть 3. Криптографические алгоритмы. Глава 11. Математические основы. 11.5. Генерация простых чисел // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 296—300. — 816 с. — 3000 экз. — ISBN 5-89392-055-4