Тест Пепина

Псевдокод $b\,\leftarrow \,3$ ОТ $i=1$ ДО $2^{n}-1$ ВЫП $b\,\leftarrow \,b^{2}{\bmod {F_{n}}}$ ЕСЛИ $b\equiv -1{\pmod {F_{n}}}$ ТО ВОЗВРАТ « $F_{n}$ — простое» ИНАЧЕ ВОЗВРАТ « $F_{n}$ — составное»

Тест Пепина — тест простоты для чисел Ферма $F_{n}.$ Тест назван в честь французского математика Феофила Пепина^[en].

Описание

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

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

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

Доказательство

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

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

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

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

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

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

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

История

Из-за большого размера чисел Ферма, тест Пепина был использован лишь 8 раз (на числах Ферма, чья простота ещё не была доказана или опровергнута)^[1]^[2]^[3]. Майер, Пападопулос и Крэндалл даже предположили, что, чтобы выполнить тесты Пепина на дальнейшних числах Ферма, понадобится несколько десятилетий, поскольку размеры ещё не исследованных чисел Ферма очень велики^[4]. По состоянию на 2023 год наименьшим непроверенным числом Ферма является $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}$ ^[5]	составное	Нет
1993	Ричард Крэндалл, Дж. Диньяс, С. Норри и Джеффри Янг	$F_{22}$ ^[6]	составное	Да (2010)
1999	Эрнст В. Майер, Джейсон С. Пападопулос и Ричард Крэндалл	$F_{24}$	составное	Нет

Примечания

↑ Conjecture 4. Fermat primes are finite — Pepin tests story, according to Leonid Durman Архивная копия от 24 сентября 2015 на Wayback Machine (англ.)
↑ Wilfrid Keller: Fermat factoring status Архивировано 10 февраля 2016 года. (англ.)
↑ R. M. Robinson (1954): Mersenne and Fermat numbers Архивная копия от 26 января 2015 на Wayback Machine (англ.)
↑ Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003), The twenty-fourth Fermat number is composite Архивная копия от 8 октября 2014 на Wayback Machine (англ.)
↑ Jeff Young & Duncan A. Buell (1988): The twentieth Fermat number is composite Архивная копия от 4 сентября 2014 на Wayback Machine, 261—263. (англ.)
↑ R. Crandall, J. Doenias, C. Norrie, and J. Young (1995): The twenty-second Fermat number is composite Архивная копия от 29 ноября 2014 на Wayback Machine, 863—868. (англ.)

Литература

Имеется викиучебник по теме «Программные реализации теста Пепина»

P. Pépin. Sur la formule $2^{2^{n}}+1$ // Comptes Rendus Acad. Sci. Paris. — 1877. — № 85. — С. 329—333.
Крэндалл Р., Померанс К. . Простые числа. — 2011. — С. 198—200.

Теоретико-числовые алгоритмы
Тесты простоты	Миллера Миллера — Рабина Люка — Лемера Пепина Агравала — Каяла — Саксены Соловея — Штрассена
Поиск простых чисел	Перебор делителей Решето Эратосфена Решето Аткина Решето Сундарама
Факторизация	Перебор делителей Метод Ферма p−1-метод Полларда ρ-алгоритм Полларда Метод Лемана Метод эллиптических кривых (алгоритм Ленстры) Алгоритм Диксона Квадратичное решето
Дискретное логарифмирование	Алгоритм Гельфонда — Шенкса Алгоритм Полига — Хеллмана ρ-метод Полларда Алгоритм «кенгуру» Полларда Алгоритм Адлемана Алгоритм COS
Нахождение НОД	Алгоритм Евклида Расширенный алгоритм Бинарный алгоритм
Арифметика по модулю	Алгоритм Монтгомери Китайская теорема об остатках
Умножение и деление чисел	Алгоритм Карацубы Алгоритм Тоома — Кука Алгоритм Шёнхаге — Штрассена Алгоритм Фюрера Алгоритм Харви — ван дер Хувена Алгоритм Бурникеля — Циглера
Вычисление квадратного корня	Алгоритм Тонелли — Шенкса Алгоритм Берлекэмпа — Рабина

Эта страница в последний раз была отредактирована 20 июня 2023 в 22:28.

Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.

Из Википедии — свободной энциклопедии

Содержание