Тест Пепіна

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

Тест Пепіна полягає в піднесенні числа ${\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(\mathrm{mod}{F}_n)}$.

Доведення. Припустимо, що рівність правильна. Тоді умова теореми Люка виконується при ${\displaystyle n=F_n}$, ${\displaystyle a=3}$, відповідно, ${\displaystyle F_n}$ є простим числом. Навпаки, нехай ${\displaystyle F_n}$ — просте число. Оскільки ${\displaystyle 2^n}$ — парне число, то ${\displaystyle 2^{2^n}\equiv 1(\mathrm{mod}3)}$, відповідно, ${\displaystyle F_n\equiv 2(\mathrm{mod}3)}$. Але ${\displaystyle F_n\equiv 1(\mathrm{mod}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 десяткових цифр. На стандартному обладнанні тест Пепіна для перевірки такого числа потребує тисячі років. На даний момент^[коли?] гостро^{[ненейтрально]} необхідні нові алгоритми для роботи з настільки величезними числами.^{[джерело?]}

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