Тест Пепіна

Псевдокод ${\displaystyle b\,\leftarrow \,3}$ ВІД ${\displaystyle i=1}$ ДО ${\displaystyle 2^{n}-1}$ ВИКОН ${\displaystyle b\,\leftarrow \,b^{2}{\bmod {F_{n}}}}$ ЯКЩО ${\displaystyle b\equiv -1{\pmod {F_{n}}}}$ ТО ПОВЕРНЕННЯ «${\displaystyle F_{n}}$ — просте» ІНАКШЕ ПОВЕРНЕННЯ «${\displaystyle F_{n}}$ — складене»

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

Опис тесту

Тест Пепіна полягає в піднесенні числа ${\displaystyle 3}$ до степені ${\displaystyle (F_{n}-1)/2=2^{2^{n}-1}}$ (${\displaystyle 2^{n}-1}$ послідовних піднесень до квадрату) по модулю ${\displaystyle F_{n}}$. Якщо результат за модулем ${\displaystyle F_{n}}$ дорівнює −1, то ${\displaystyle F_{n}}$ є простим, а в іншому випадку — складеним.

Тест базується на наступній теоремі:

Теорема. При n ≥ 1 число Ферма ${\displaystyle F_{n}=2^{2^{n}}+1}$ є простим тоді й тільки тоді, коли ${\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}}$.

Доведення. Припустимо, що рівність правильна. Тоді умова теореми Люка виконується при ${\displaystyle n=F_{n}}$, ${\displaystyle a=3}$, відповідно, ${\displaystyle F_{n}}$ є простим числом. Навпаки, нехай ${\displaystyle F_{n}}$ — просте число. Оскільки ${\displaystyle 2^{n}}$ — парне число, то ${\displaystyle 2^{2^{n}}\equiv 1{\pmod {3}}}$, відповідно, ${\displaystyle F_{n}\equiv 2{\pmod {3}}}$. Але ${\displaystyle F_{n}\equiv 1{\pmod {4}}}$, тому символ Лежандра ${\displaystyle \left({\frac {3}{F_{n}}}\right)}$ рівний −1. Звідси випливає, що 3 не є квадратичним лишком по модулю ${\displaystyle F_{n}}$. Необхідне порівняння випливає з критерію Ейлера.

Варіації та узагальнення

Тест Пепіна є частинним випадком тесту Люка.

Число 3 у тесті Пепіна може бути замінено на 5, 6, 7 чи 10 (послідовність A129802 з Онлайн енциклопедії послідовностей цілих чисел, OEIS), які також є первісними коренями за модулем кожного простого числа Ферма.

Відомо, що Пепін представив критерій з числом 5, а не з числом 3. Прот и Люка відзначили, що також можна застосувати число 3.

Складність обчислень

Оскільки тест Пепіна вимагає ${\displaystyle 2^{n}-1}$ піднесень до квадрату за модулем ${\displaystyle F_{n}}$, то він виконується за поліноміальний час від довжини числа ${\displaystyle F_{n}}$. Проте, якщо на вхід подається лише число n, то тест Пепіна виконується за над-експоненційний час від довжини входу (${\displaystyle \log n}$).

Історія

Через великий розмір чисел Ферма, тест Пепіна був застосований лише 8 разів (для чисел Ферма, чия простота ще не була доведена чи спростована)[1][2][3]. 2003 року, після тестування двадцять четвертого числа Ферма (${\displaystyle F_{24}}$), Майер, Пападопулос і Крендалл висунули припущення, що мине декілька десятків років, перш ніж технології дозволять виконати тести Пепіна для ще недосліджених чисел Ферма, бо їх розміри надто великі[4]. На листопад 2014 року найменшим неперевіреним числом Ферма було ${\displaystyle F_{33}}$, яке містить 2 585 827 973 десяткових цифр. На стандартному обладнанні тест Пепіна для перевірки такого числа потребує тисячі років. На даний момент^[коли?] гостро^[ненейтрально] необхідні нові алгоритми для роботи з настільки величезними числами.^[джерело?]

Рік	Дослідники	Числа Ферма	Результати тесту Пепіна	Чи знайдений дільник?
1905	Джеймс С. Морхед і Альфред Вестерн	${\displaystyle F_{7}}$	складене	Так (1970)
1909	Джеймс С. Морхед і Альфред Вестерн	${\displaystyle F_{8}}$	складене	Так (1980)
1952	Рафаель М. Робінсон	${\displaystyle F_{10}}$	складене	Так (1953)
1960	Г. А. Паксон	${\displaystyle F_{13}}$	складене	Так (1974)
1961	Джон Селфрідж і Олександр Гурвіц	${\displaystyle F_{14}}$	складене	Так (2010)
1987	Дункан Бьюел і Джеффрі Янг	${\displaystyle F_{20}}$[5]	складене	Ні
1993	Річард Крендалл, Дж. Діньяс, С. Норрі і Джеффрі Янг	${\displaystyle F_{22}}$[6]	складене	Так (2010)
1999	Ернст В. Майер, Джейсон С. Пападопулос і Річард Крендалл	${\displaystyle F_{24}}$	складене	Ні

Примітки

1. Conjecture 4. Fermat primes are finite — Pepin tests story, according to Leonid Durman(англ.)
2. Wilfrid Keller: Fermat factoring status [Архівовано 10 лютого 2016 у Wayback Machine.](англ.)
3. R. M. Robinson (1954): Mersenne and Fermat numbers(англ.)
4. Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003), The twenty-fourth Fermat number is composite(англ.)
5. Jeff Young & Duncan A. Buell (1988): The twentieth Fermat number is composite, 261—263.(англ.)
6. R. Crandall, J. Doenias, C. Norrie, and J. Young (1995): The twenty-second Fermat number is composite, 863—868.(англ.)

Література

• P. Pépin. Sur la formule ${\displaystyle 2^{2^{n}}+1}$. — Comptes Rendus Acad. Sci. Paris, 1877. — № 85.
• Крэндалл Р., Померанс К. . Простые числа. — 2011. — С. 198—200.