Тест Пепина

Тест Пепина — тест простоты для чисел Ферма ${\displaystyle F_{n}.}$ Тест назван в честь французского математика Феофила Пепина^[англ.].

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

Описание

Число ${\displaystyle 3}$ нужно возвести в степень ${\displaystyle (F_{n}-1)/2=2^{2^{n}-1}}$ (в некоторых алгоритмах это реализуется с помощью серии из ${\displaystyle 2^{n}-1}$ последовательных возведений в квадрат) по модулю ${\displaystyle F_{n}}$. Если результат сравним по модулю ${\displaystyle F_{n}}$ с −1, то ${\displaystyle F_{n}}$ является простым, а в противном случае — составным.

Это утверждение представляет собой следующую теорему:

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

Доказательство

Предположим, что сравнение верно. Тогда условие теоремы Люка выполняется при ${\displaystyle n=F_{n}}$, ${\displaystyle a=3}$, следовательно, ${\displaystyle F_{n}}$ является простым числом. Обратно, пусть ${\displaystyle F_{n}}$ — простое число. Так как ${\displaystyle 2^{n}}$ — четное число, то ${\displaystyle 2^{2^{n}}\equiv 1{\pmod {3}}}$, следовательно, ${\displaystyle F_{n}\equiv 2{\pmod {3}}}$. Но ${\displaystyle F_{n}\equiv 1{\pmod {4}}}$, поэтому символ Лежандра ${\displaystyle \left({\frac {3}{F_{n}}}\right)}$ равен −1. Следовательно, 3 не является квадратичным вычетом по модулю ${\displaystyle F_{n}}$. Необходимое сравнение следует из критерия Эйлера.■

Вариации и обобщения

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

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

Известно, что Пепин привёл критерий с числом 5 вместо числа 3. Прот и Люка отметили, что можно также использовать число 3.

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

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

История

Из-за большого размера чисел Ферма, тест Пепина был использован лишь 8 раз (на числах Ферма, чья простота ещё не была доказана или опровергнута)^[1][2][3]. Майер, Пападопулос и Крэндалл даже предположили, что, чтобы выполнить тесты Пепина на дальнейшних числах Ферма, понадобится несколько десятилетий, поскольку размеры ещё не исследованных чисел Ферма очень велики^[4]. По состоянию на 2023 год наименьшим непроверенным числом Ферма является ${\displaystyle F_{33}}$, которое содержит 2 585 827 973 десятичных цифр. На стандартном оборудовании потребуются тысячи лет, чтобы тест Пепина проверил такое число, и для работы со столь огромными числами Ферма возникает острая нужда в новых алгоритмах.

Год	Исследователи	Число Ферма	Результат теста Пепина	Удалось ли найти делитель?
1905	Джеймс С. Морхед и Альфред Вестерн	${\displaystyle F_{7}}$	составное	Да (1970)
1909	Джеймс С. Морхед и Альфред Вестерн	${\displaystyle F_{8}}$	составное	Да (1980)
1952	Рафаэль М. Робинсон	${\displaystyle F_{10}}$	составное	Да (1953)
1960	Г. А. Паксон	${\displaystyle F_{13}}$	составное	Да (1974)
1961	Джон Селфридж и Александр Гурвиц	${\displaystyle F_{14}}$	составное	Да (2010)
1987	Дункан Бьюэл и Джеффри Янг	${\displaystyle F_{20}}$[5]	составное	Нет
1993	Ричард Крэндалл, Дж. Диньяс, С. Норри и Джеффри Янг	${\displaystyle F_{22}}$[6]	составное	Да (2010)
1999	Эрнст В. Майер, Джейсон С. Пападопулос и Ричард Крэндалл	${\displaystyle F_{24}}$	составное	Нет