Написано: 01 Жовтня 2009 15:06 Тема повідомлення: тест
Тест Пепина — полиномиальный тест простоты для чисел Ферма.
Тест Пепина базируется на следующем утверждении, которое немедленно следует из квадратичного закона взаимности:
число 3 является первообразным корнем по модулю каждого простого числа Ферма.
Поэтому
число ФермаFn=22n+1является простым тогда и только тогда, когда3(Fn-1)/2=-1(mod Fn)
Тест Пепина состоит в возведении числа 3 в степень (Fn-1)/2=22n-1(серией из 2n − 1 последовательных возведений в квадрат) по модулю Fn и сравнении результата с -1.
Число 3 в тесте Пепина может быть заменено на 5, 6, 7 или 10 (последовательность A129802 в OEIS), которые также являются первообразными корнями по модулю каждого простого числа Ферма.
Հայերեն
Беларуская
Nederlands
English
Français
ქართული
Deutsch
Lietuvių
Русский
Українська
тест 
