PROFILPELAJAR.COM

Псевдокод

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

Примітки

↑ Conjecture 4. Fermat primes are finite — Pepin tests story, according to Leonid Durman(англ.)
↑ Wilfrid Keller: Fermat factoring status [Архівовано 10 лютого 2016 у Wayback Machine.](англ.)
↑ R. M. Robinson (1954): Mersenne and Fermat numbers(англ.)
↑ Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003), The twenty-fourth Fermat number is composite(англ.)
↑ Jeff Young & Duncan A. Buell (1988): The twentieth Fermat number is composite, 261—263.(англ.)
↑ 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 $2^{2^{n}}+1$ . — Comptes Rendus Acad. Sci. Paris, 1877. — № 85.
Крэндалл Р., Померанс К. . Простые числа. — 2011. — С. 198—200.