Викия

Математика

Тест Пепина

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Алгоритм на псевдокоде Править

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

Тест Пепина состоит в возведении числа 3 в степень (F_n - 1)/2 = 2^{2^n-1} по модулю F_n (серией из 2^n-1 последовательных возведений в квадрат) и сравнении результата с -1.

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

Викия-сеть

Случайная вики