Тест Пепина
|
Тест Пепина — тест простоты для чисел Ферма <math>F_n.</math> Тест назван в честь французского математика Шаблон:Нп5.
Описание
Число <math>3</math> нужно возвести в степень <math>(F_n - 1)/2 = 2^{2^n-1}</math> (в некоторых алгоритмах это реализуется с помощью серии из <math>2^n-1</math> последовательных возведений в квадрат) по модулю <math>F_n</math>. Если результат сравним по модулю <math>F_n</math> с −1, то <math>F_n</math> является простым, а в противном случае — составным.
Это утверждение представляет собой следующую теорему:
Теорема. При Шаблон:Числочисло Ферма <math>F_n = 2^{2^n}+1</math> является простым тогда и только тогда, когда <math>3^{(F_n-1)/2}\equiv-1\pmod{F_n}</math>.
Вариации и обобщения
Тест Пепина является частным случаем теста Люка.
Число 3 в тесте Пепина может быть заменено на 5, 6, 7 или 10 (последовательность A129802 в OEIS), которые также являются первообразными корнями по модулю каждого простого числа Ферма.
Известно, что Пепин привёл критерий с числом 5 вместо числа 3. Прот и Люка отметили, что можно также использовать число 3.
Вычислительная сложность
Так как тест Пепина требует <math>2^n-1</math> возведений в квадрат по модулю <math>F_n</math>, то он выполняется за время, имеющее полиномиальную зависимость от длины числа <math>F_n,</math> но сверхэкспоненциальную относительно длины числа n (<math>\log n</math>).
История
Из-за большого размера чисел Ферма, тест Пепина был использован лишь 8 раз (на числах Ферма, чья простота ещё не была доказана или опровергнута)<ref>Conjecture 4. Fermat primes are finite — Pepin tests story, according to Leonid Durman Шаблон:WaybackШаблон:Ref</ref><ref>Wilfrid Keller: Fermat factoring status Шаблон:WebarchiveШаблон:Ref</ref><ref>R. M. Robinson (1954): Mersenne and Fermat numbers Шаблон:WaybackШаблон:Ref</ref>. Майер, Пападопулос и Крэндалл даже предположили, что, чтобы выполнить тесты Пепина на дальнейшних числах Ферма, понадобится несколько десятилетий, поскольку размеры ещё не исследованных чисел Ферма очень велики<ref>Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003), The twenty-fourth Fermat number is composite Шаблон:WaybackШаблон:Ref</ref>. По состоянию Шаблон:На наименьшим непроверенным числом Ферма является <math>F_{33}</math>, которое содержит 2 585 827 973 десятичных цифр. На стандартном оборудовании потребуются тысячи лет, чтобы тест Пепина проверил такое число, и для работы со столь огромными числами Ферма возникает острая нужда в новых алгоритмах.
| Год | Исследователи | Число Ферма | Результат теста Пепина | Удалось ли найти делитель? |
|---|---|---|---|---|
| 1905 | Джеймс С. Морхед и Альфред Вестерн | <math>F_{7}</math> | составное | Да (1970) |
| 1909 | Джеймс С. Морхед и Альфред Вестерн | <math>F_{8}</math> | составное | Да (1980) |
| 1952 | Рафаэль М. Робинсон | <math>F_{10}</math> | составное | Да (1953) |
| 1960 | Г. А. Паксон | <math>F_{13}</math> | составное | Да (1974) |
| 1961 | Джон Селфридж и Александр Гурвиц | <math>F_{14}</math> | составное | Да (2010) |
| 1987 | Дункан Бьюэл и Джеффри Янг | <math>F_{20}</math><ref>Jeff Young & Duncan A. Buell (1988): The twentieth Fermat number is composite Шаблон:Wayback, 261—263.Шаблон:Ref</ref> | составное | Нет |
| 1993 | Ричард Крэндалл, Дж. Диньяс, С. Норри и Джеффри Янг | <math>F_{22}</math><ref>R. Crandall, J. Doenias, C. Norrie, and J. Young (1995): The twenty-second Fermat number is composite Шаблон:Wayback, 863—868.Шаблон:Ref</ref> | составное | Да (2010) |
| 1999 | Эрнст В. Майер, Джейсон С. Пападопулос и Ричард Крэндалл | <math>F_{24}</math> | составное | Нет |
Примечания
Литература
Шаблон:Родственный проект{{#if:||{{#if:Программные реализации теста Пепина||}}}}