Тест Пепина

Псевдокод $b\leftarrow 3$ ОТ $i=1$ ДО $2^n-1$ ВЫП $b\leftarrow b^{2}mod{F}_n$ ЕСЛИ $b\equiv -1(\mathrm{mod}{F}_n)$ ТО ВОЗВРАТ «$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$ является простым, а в противном случае — составным.

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

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

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

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

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

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

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

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

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

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

История

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

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

Литература

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