Тест Пепіна

Псевдокод ${\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 разів (для чисел Ферма, чия простота ще не була доведена чи спростована). 2003 року, після тестування двадцять четвертого числа Ферма (${\displaystyle F_{24}}$), Майер, Пападопулос і Крендалл висунули припущення, що мине декілька десятків років, перш ніж технології дозволять виконати тести Пепіна для ще недосліджених чисел Ферма, бо їх розміри надто великі. На листопад 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}}$	складене	Ні
1993	Річард Крендалл, Дж. Діньяс, С. Норрі і Джеффрі Янг	${\displaystyle F_{22}}$	складене	Так (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.