Тест Пепена - Pépin's test

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

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

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

{\ 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, 3117279402881, 17172794012801, 1717274840288 . (последовательность A102742 в OEIS )

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

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

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

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

{\ Displaystyle 3 ^ {(F_ {n} -1) / 2} \ Equiv -1 {\ pmod {F_ {n}}}}

держит. Тогда , таким образом, мультипликативный порядок 3 по модулю делится , что является степенью двойки. С другой стороны, порядок не делится , поэтому он должен быть равен . В частности, есть по крайней мере числа ниже взаимно простых , и это может произойти, только если оно простое. ${\ Displaystyle 3 ^ {F_ {n} -1} \ Equiv 1 {\ pmod {F_ {n}}}}$ ${\ 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}}}}

,

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

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

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

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