Тест Пепіна

Тест Пепіна полягає в піднесенні числа ${\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}}$	складене	Ні

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