Тест Пепина

Псевдокод ${\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 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}}$	составное	Нет

Примечания

1. Conjecture 4. Fermat primes are finite — Pepin tests story, according to Leonid Durman Архивная копия от 24 сентября 2015 на Wayback Machine (англ.)
2. Wilfrid Keller: Fermat factoring status Архивировано 10 февраля 2016 года. (англ.)
3. R. M. Robinson (1954): Mersenne and Fermat numbers Архивная копия от 26 января 2015 на Wayback Machine (англ.)
4. Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003), The twenty-fourth Fermat number is composite Архивная копия от 8 октября 2014 на Wayback Machine (англ.)
5. Jeff Young & Duncan A. Buell (1988): The twentieth Fermat number is composite Архивная копия от 4 сентября 2014 на Wayback Machine, 261—263. (англ.)
6. R. Crandall, J. Doenias, C. Norrie, and J. Young (1995): The twenty-second Fermat number is composite Архивная копия от 29 ноября 2014 на Wayback Machine, 863—868. (англ.)

Литература

• P. Pépin. Sur la formule ${\displaystyle 2^{2^{n}}+1}$ // Comptes Rendus Acad. Sci. Paris. — 1877. — № 85. — С. 329—333.
• Крэндалл Р., Померанс К. . Простые числа. — 2011. — С. 198—200.