Тест Пепина

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

Псевдокод

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 — составное»

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

Описание[править | править вики-текст]

Тест Пепина состоит в возведении числа 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}.

Вариации и обобщения[править | править вики-текст]

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

Число 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] На ноябрь 2014 года наименьшим непроверенным числом Ферма является 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} составное Нет

Примечания[править | править вики-текст]

  1. Conjecture 4. Fermat primes are finite — Pepin tests story, according to Leonid Durman (англ.)
  2. Wilfrid Keller: Fermat factoring status (англ.)
  3. R. M. Robinson (1954): Mersenne and Fermat numbers (англ.)
  4. Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003), The twenty-fourth Fermat number is composite (англ.)
  5. Jeff Young & Duncan A. Buell (1988): The twentieth Fermat number is composite, 261—263. (англ.)
  6. R. Crandall, J. Doenias, C. Norrie, and J. Young (1995): The twenty-second Fermat number is composite, 863—868. (англ.)

Литература[править | править вики-текст]

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