Тест Пепина

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

Описание

Псевдокод $b\,\leftarrow\, 3$ ОТ $i=1$ ДО $2^n-1$ ВЫП $b\,\leftarrow\, b^2\bmod{F_n}$ ЕСЛИ $b\equiv -1\pmod{F_n}$ ТО ВОЗВРАТ «$F_n$ — простое» ИНАЧЕ ВОЗВРАТ «$F_n$ — составное»

Тест Пепина состоит в возведении числа $3$ в степень $(F_n - 1)/2 = 2^{2^n-1}$ (серией из $2^n-1$ последовательных возведений в квадрат) по модулю $F_n$. Если результат сравним по модулю $F_n$ с -1, то $F_n$ является простым, а в противном случае — составным.

Тест Пепина является частным случаем теста Люка

Обоснование

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

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

Поэтому

число Ферма $F_n = 2^{2^n}+1$ является простым тогда и только тогда, когда $3^{(F_n - 1)/2}\equiv -1\pmod{F_n}$.

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

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

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