Тест Пепина

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

Тест Пепина — тест простоты для чисел Ферма.

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

Псевдокод

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 является простым, а в противном случае — составным.

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

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

Тест Пепина базируется на следующем следствии квадратичного закона взаимности:

число 3 является первообразным корнем по модулю каждого простого числа Ферма.

Поэтому

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

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

Вычислительная сложность[править | править вики-текст]

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

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

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

Год Исследователи Числа Ферма Результаты теста Пепина Делитель найден в последствии?
1905 Морхед & Вестерн F_{7} составное Да (1970)
1909 Морхед и Вестерн F_{8} составное Да (1980)
1952 Robinson F_{10} составное Да (1953)
1960 Paxson F_{13} составное Да (1974)
1961 Selfridge & Hurwitz F_{14} составное Да (2010)
1987 Buell & Young F_{20} составное Нет
1993 Крэндалл, Doenias, Norrie & Young F_{22} составное Да (2010)
1999 Mayer, Papadopoulos и Крэндалл F_{24} составное Нет

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

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

  • P. Pépin, Sur la formule 2^{2^n}+1, Comptes Rendus Acad. Sci. Paris 85 (1877), pp. 329—333.