Тест Пепена - Pépins test - Wikipedia

В математика, Тест Пепина это тест на простоту, по которому можно определить, Число Ферма является основной. Это вариант Тест прота. Тест назван в честь французского математика, Теофиль Пепен.

Описание теста

Позволять ${\displaystyle F_{n}=2^{2^{n}}+1}$ быть пое число Ферма. Тест Пепина утверждает, что для п > 0,

${\displaystyle F_{n}}$ прост тогда и только тогда, когда ${\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}.}$

Выражение ${\displaystyle 3^{(F_{n}-1)/2}}$ можно оценить по модулю ${\displaystyle F_{n}}$ к повторное возведение в квадрат. Это делает тест быстрым полиномиальное время алгоритм. Однако числа Ферма растут так быстро, что лишь небольшую часть чисел Ферма можно проверить в разумные сроки и в разумных пределах.

Другие базы могут использоваться вместо 3, эти базы

3, 5, 6, 7, 10, 12, 14, 20, 24, 27, 28, 39, 40, 41, 45, 48, 51, 54, 56, 63, 65, 75, 78, 80, 82, 85, 90, 91, 96, 102, 105, 108, 112, 119, 125, 126, 130, 147, 150, 156, 160, ... (последовательность A129802 в OEIS ).

Простые числа в указанной выше последовательности называются Элитные простые числа, они есть

3, 5, 7, 41, 15361, 23041, 26881, 61441, 87041, 163841, 544001, 604801, 6684673, 14172161, 159318017, 446960641, 1151139841, 3208642561, 38126223361, 108905103361, 3117279401280, 3117279402881, 171727940288 . (последовательность A102742 в OEIS )

Для целого числа б > 1, база б может использоваться тогда и только тогда, когда только конечное число чисел Ферма F_п удовлетворяет это ${\displaystyle \left({\frac {b}{F_{n}}}\right)=1}$, куда ${\displaystyle \left({\frac {b}{F_{n}}}\right)}$ это Символ Якоби.

Фактически, тест Пепена такой же, как и Тест Эйлера-Якоби для чисел Ферма, поскольку символ Якоби ${\displaystyle \left({\frac {b}{F_{n}}}\right)}$ равно −1, т.е. нет чисел Ферма, которые являются псевдопростыми числами Эйлера-Якоби для этих базисов, перечисленных выше.

Доказательство правильности

Достаточность: предположим, что сравнение

${\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}}$

держит. потом ${\displaystyle 3^{F_{n}-1}\equiv 1{\pmod {F_{n}}}}$, Таким образом мультипликативный порядок из 3 по модулю ${\displaystyle F_{n}}$ разделяет ${\displaystyle F_{n}-1=2^{2^{n}}}$, что является степенью двойки. С другой стороны, порядок не делит ${\displaystyle (F_{n}-1)/2}$, а значит, он должен быть равен ${\displaystyle F_{n}-1}$. В частности, есть не менее ${\displaystyle F_{n}-1}$ числа ниже ${\displaystyle F_{n}}$ взаимно простой с ${\displaystyle F_{n}}$, а это может произойти, только если ${\displaystyle F_{n}}$ простое.

Необходимость: предположим, что ${\displaystyle F_{n}}$ простое. К Критерий Эйлера,

${\displaystyle 3^{(F_{n}-1)/2}\equiv \left({\frac {3}{F_{n}}}\right){\pmod {F_{n}}}}$,

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

Исторические тесты Пепена

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

Год	Пруверы	Число Ферма	Результат теста Пепина	Фактор найден позже?
1905	Morehead & Западный	${\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	Buell & Молодой	${\displaystyle F_{20}}$	составной	Нет
1993	Crandall, Дениас, Норри и Янг	${\displaystyle F_{22}}$	составной	Да (2010)
1999	Майер, Пападопулос и Крэндалл	${\displaystyle F_{24}}$	составной	Нет

Примечания

1. Гипотеза 4. Простые числа Ферма конечны - история тестов Пепина, по словам Леонида Дурмана
2. Уилфрид Келлер: Статус факторинга Fermat
3. Р. М. Робинсон (1954): Числа Мерсенна и Ферма
4. Ричард Э. Крэндалл, Эрнст В. Майер и Джейсон С. Пападопулос, Двадцать четвертое число Ферма составное (2003 г.)

Рекомендации

• П. Пепин, Sur la Formule ${\displaystyle 2^{2^{n}}+1}$, Comptes rendus de l'Académie des Sciences de Paris 85 (1877), стр. 329–333.

внешняя ссылка

• Главный глоссарий: тест Пепина