Тест Пепина

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

b\,\leftarrow\, 3
FOR i = 1 TO 2n − 1 DO b\,\leftarrow\, b^2\bmod{F_n}
IF b\equiv -1\pmod{F_n} THEN
RETURN «Fn — простое»
ELSE
RETURN «Fn — составное»

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

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

число 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} по модулю Fn (серией из 2n − 1 последовательных возведений в квадрат) и сравнении результата с - 1.

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

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home