Тест Пепина

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

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

Описание[править | править исходный текст]

Псевдокод

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).