WikiSort.ru - Не сортированное

Тест Пепина — тест простоты для чисел Ферма. Тест назван в честь французского математика Феофила Пепина.

Описание

Тест Пепина состоит в возведении числа ${\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]. На ноябрь 2014 года наименьшим непроверенным числом Ферма является ${\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.