Псевдокод
ОТ ДО ВЫП ЕСЛИ ТО ВОЗВРАТ « — простое» ИНАЧЕ ВОЗВРАТ « — составное»
Тест Пепина — тест простоты для чисел Ферма Тест назван в честь французского математика .
Описание
Число нужно возвести в степень (в некоторых алгоритмах это реализуется с помощью серии из последовательных возведений в квадрат) по модулю . Если результат сравним по модулю с −1, то является простым, а в противном случае — составным.
Это утверждение представляет собой следующую теорему:
Теорема. При число Ферма является простым тогда и только тогда, когда .
Вариации и обобщения Тест Пепина является частным случаем теста Люка.
Число 3 в тесте Пепина может быть заменено на 5, 6, 7 или 10 (), которые также являются первообразными корнями по модулю каждого простого числа Ферма.
Известно, что Пепин привёл критерий с числом 5 вместо числа 3. Прот и Люка отметили, что можно также использовать число 3.
Вычислительная сложность Так как тест Пепина требует возведений в квадрат по модулю , то он выполняется за время, имеющее полиномиальную зависимость от длины числа но сверхэкспоненциальную относительно длины числа n ().
История Из-за большого размера чисел Ферма, тест Пепина был использован лишь 8 раз (на числах Ферма, чья простота ещё не была доказана или опровергнута)Conjecture 4. Fermat primes are finite — Pepin tests story, according to Leonid Durman Wilfrid Keller: Fermat factoring status R. M. Robinson (1954): Mersenne and Fermat numbers . Майер, Пападопулос и Крэндалл даже предположили, что, чтобы выполнить тесты Пепина на дальнейшних числах Ферма, понадобится несколько десятилетий, поскольку размеры ещё не исследованных чисел Ферма очень великиRichard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003), The twenty-fourth Fermat number is composite . По состоянию наименьшим непроверенным числом Ферма является , которое содержит десятичных цифр. На стандартном оборудовании потребуются тысячи лет, чтобы тест Пепина проверил такое число, и для работы со столь огромными числами Ферма возникает острая нужда в новых алгоритмах.
Год Исследователи Число Ферма Результат теста Пепина Удалось ли найти делитель? 1905 Джеймс С. Морхед и Альфред Вестерн составное Да (1970) 1909 Джеймс С. Морхед и Альфред Вестерн составное Да (1980) 1952 Рафаэль М. Робинсон составное Да (1953) 1960 Г. А. Паксон составное Да (1974) 1961 Джон Селфридж и Александр Гурвиц составное Да (2010) 1987 Дункан Бьюэл и Джеффри Янг Jeff Young & Duncan A. Buell (1988): The twentieth Fermat number is composite , 261—263. составное Нет 1993 Ричард Крэндалл, Дж. Диньяс, С. Норри и Джеффри Янг R. Crandall, J. Doenias, C. Norrie, and J. Young (1995): The twenty-second Fermat number is composite , 863—868. составное Да (2010) 1999 Эрнст В. Майер, Джейсон С. Пападопулос и Ричард Крэндалл составное Нет
Примечания
Литература
Категория:Тесты простоты