Тест Пепина — тест простоты для чисел Ферма.

Описание

Тест Пепина состоит в возведении числа в степень (серией из последовательных возведений в квадрат) по модулю . Если результат сравним по модулю с -1, то является простым, а в противном случае — составным.

Обоснование

Тест Пепина базируется на следующем следствии квадратичного закона взаимности:

число 3 является первообразным корнем по модулю каждого простого числа Ферма.

Поэтому

число Ферма является простым тогда и только тогда, когда .

Число 3 в тесте Пепина может быть заменено на 5, 6, 7 или 10 (последовательность A129802 в OEIS), которые также являются первообразными корнями по модулю каждого простого числа Ферма.

Вычислительная сложность

Так как тест Пепина требует возведений в квадрат по модулю , то он выполняется за полиномиальное время от длины числа . Однако, если на вход подается лишь число n, то тест Пепина выполняется за сверх-экспоненциальное время от длины входа ().