тест Пепина

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

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

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

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

Выражение $3^{(F_{n}-1)/2}$ можно оценить по модулю $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, 171727482881, 318093312001, 443069456129, 912680550401, ... (последовательность A102742 в OEIS )

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

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

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

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

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

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

Необходимость: предположим, что $F_{n}$ является простым. По критерию Эйлера ,

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

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

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

Из-за редкости чисел Ферма тест Пепена проводился только восемь раз (на числах Ферма, статус простоты которых еще не был известен). Майер, Пападопулос и Крэндалл предполагают, что на самом деле из-за размера до сих пор неопределенных чисел Ферма потребуются значительные достижения в технологии, прежде чем можно будет провести новые тесты Пепина в разумные сроки.

Год	Пруверы	Число Ферма	Результат теста на глюк	Фактор найден позже?
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}$	композитный	Нет

Ссылки

• П. Пепен, О формуле $2^{2^{n}}+1$, Отчеты Парижской академии наук 85 (1877), стр. 329–333.

Внешние ссылки

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