Тест Пепина
Тест Пепина — тест простоты для чисел Ферма  Тест назван в честь французского математика .

Описание 

Число  нужно возвести в степень  (в некоторых алгоритмах это реализуется с помощью серии из  последовательных возведений в квадрат) по модулю . Если результат сравним по модулю  с −1, то  является простым, а в противном случае — составным.

Это утверждение представляет собой следующую теорему:

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

Вариации и обобщения 
Тест Пепина является частным случаем теста Люка.

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

Известно, что Пепин привёл критерий с числом 5 вместо числа 3. Прот и Люка отметили, что можно также использовать число 3.

Вычислительная сложность 
Так как тест Пепина требует  возведений в квадрат по модулю , то он выполняется за время, имеющее полиномиальную зависимость от длины числа  но сверхэкспоненциальную относительно длины числа n ().

История 
Из-за большого размера чисел Ферма, тест Пепина был использован лишь 8 раз (на числах Ферма, чья простота ещё не была доказана или опровергнута). Майер, Пападопулос и Крэндалл даже предположили, что, чтобы выполнить тесты Пепина на дальнейшних числах Ферма, понадобится несколько десятилетий, поскольку размеры ещё не исследованных чисел Ферма очень велики. По состоянию  наименьшим непроверенным числом Ферма является , которое содержит  десятичных цифр. На стандартном оборудовании потребуются тысячи лет, чтобы тест Пепина проверил такое число, и для работы со столь огромными числами Ферма возникает острая нужда в новых алгоритмах.

Примечания

Литература 

 
 

Тесты простоты