Тест Пепина

Псевдокод $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.$ Тест назван в честь французского математика Шаблон:Нп5.

Описание

Число $3$ нужно возвести в степень $(F_n-1)/2=2^{2^n-1}$ (в некоторых алгоритмах это реализуется с помощью серии из $2^n-1$ последовательных возведений в квадрат) по модулю $F_n$. Если результат сравним по модулю $F_n$ с −1, то $F_n$ является простым, а в противном случае — составным.

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

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

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

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

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

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

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

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

История

Из-за большого размера чисел Ферма, тест Пепина был использован лишь 8 раз (на числах Ферма, чья простота ещё не была доказана или опровергнута). Майер, Пападопулос и Крэндалл даже предположили, что, чтобы выполнить тесты Пепина на дальнейшних числах Ферма, понадобится несколько десятилетий, поскольку размеры ещё не исследованных чисел Ферма очень велики. По состоянию Шаблон:На наименьшим непроверенным числом Ферма является $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}$	составное	Нет

Литература

• Шаблон:Статья
• Шаблон:Книга