- Тест Пепина
-
Тест Пепина — тест простоты для чисел Ферма.
Описание
- ОТ ДО ВЫП
- ЕСЛИ ТО
- ВОЗВРАТ « — простое»
- ИНАЧЕ
- ВОЗВРАТ « — составное»
Тест Пепина состоит в возведении числа в степень (серией из последовательных возведений в квадрат) по модулю . Если результат сравним по модулю с -1, то является простым, а в противном случае — составным.
Тест Пепина является частным случаем теста Люка
Обоснование
Тест Пепина базируется на следующем следствии квадратичного закона взаимности:
- число 3 является первообразным корнем по модулю каждого простого числа Ферма.
Поэтому
- число Ферма является простым тогда и только тогда, когда .
Число 3 в тесте Пепина может быть заменено на 5, 6, 7 или 10 (последовательность A129802 в OEIS), которые также являются первообразными корнями по модулю каждого простого числа Ферма.
Вычислительная сложность
Так как тест Пепина требует возведений в квадрат по модулю , то он выполняется за полиномиальное время от длины числа . Однако, если на вход подается лишь число n, то тест Пепина выполняется за сверх-экспоненциальное время от длины входа ().
Категория:- Тесты простоты
Wikimedia Foundation. 2010.