Тест Пепина

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

[править] Алгоритм на псевдокоде FOR i = 1 TO 2n − 1 DO IF THEN RETURN «Fn — простое» ELSE RETURN «Fn — составное»

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

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

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

Поэтому

число Ферма является простым тогда и только тогда, когда .

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

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