Тест Пепина — Википедия

Тест Пепина — тест простоты для чисел Ферма ${\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}}}}$.

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

Число 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}}$	составное	Нет

	Имеется викиучебник по теме «Программные реализации теста Пепина»

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