Тест Пепина

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Псевдокод

ОТ ДО ВЫП
ЕСЛИ ТО
ВОЗВРАТ « — простое»
ИНАЧЕ
ВОЗВРАТ « — составное»

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

Число нужно возвести в степень (в некоторых алгоритмах это реализуется с помощью серии из последовательных возведений в квадрат) по модулю . Если результат сравним по модулю с −1, то является простым, а в противном случае — составным.

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

Теорема. При n ≥ 1'число Ферма является простым тогда и только тогда, когда .

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

[править | править код]

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

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

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

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

[править | править код]

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

Из-за большого размера чисел Ферма, тест Пепина был использован лишь 8 раз (на числах Ферма, чья простота ещё не была доказана или опровергнута)[1][2][3]. Майер, Пападопулос и Крэндалл даже предположили, что, чтобы выполнить тесты Пепина на дальнейшних числах Ферма, понадобится несколько десятилетий, поскольку размеры ещё не исследованных чисел Ферма очень велики[4]. По состоянию на 2023 год наименьшим непроверенным числом Ферма является , которое содержит 2 585 827 973 десятичных цифр. На стандартном оборудовании потребуются тысячи лет, чтобы тест Пепина проверил такое число, и для работы со столь огромными числами Ферма возникает острая нужда в новых алгоритмах.

Год Исследователи Число Ферма Результат теста Пепина Удалось ли найти делитель?
1905 Джеймс С. Морхед и Альфред Вестерн составное Да (1970)
1909 Джеймс С. Морхед и Альфред Вестерн составное Да (1980)
1952 Рафаэль М. Робинсон составное Да (1953)
1960 Г. А. Паксон составное Да (1974)
1961 Джон Селфридж и Александр Гурвиц составное Да (2010)
1987 Дункан Бьюэл и Джеффри Янг [5] составное Нет
1993 Ричард Крэндалл, Дж. Диньяс, С. Норри и Джеффри Янг [6] составное Да (2010)
1999 Эрнст В. Майер, Джейсон С. Пападопулос и Ричард Крэндалл составное Нет

Примечания

[править | править код]
  1. Conjecture 4. Fermat primes are finite — Pepin tests story, according to Leonid Durman Архивная копия от 24 сентября 2015 на Wayback Machine (англ.)
  2. Wilfrid Keller: Fermat factoring status Архивировано 10 февраля 2016 года. (англ.)
  3. R. M. Robinson (1954): Mersenne and Fermat numbers Архивная копия от 26 января 2015 на Wayback Machine (англ.)
  4. Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003), The twenty-fourth Fermat number is composite Архивная копия от 8 октября 2014 на Wayback Machine (англ.)
  5. Jeff Young & Duncan A. Buell (1988): The twentieth Fermat number is composite Архивная копия от 4 сентября 2014 на Wayback Machine, 261—263. (англ.)
  6. 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  // Comptes Rendus Acad. Sci. Paris. — 1877. — № 85. — С. 329—333.
  • Крэндалл Р., Померанс К. . Простые числа. — 2011. — С. 198—200.