Тест Пепіна

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

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

Опис тесту

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

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

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

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

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

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

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

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

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

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

Історія

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

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

Література

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