Псевдокод
ВІД ДО ВИКОН ЯКЩО ТО ПОВЕРНЕННЯ « — просте» ІНАКШЕ ПОВЕРНЕННЯ « — складене»
Тест Пепіна — тест простоти для чисел Ферма. Тест названий на честь французького математика Теофіла Пепіна.
Опис тесту
Тест Пепіна полягає в піднесенні числа до степені ( послідовних піднесень до квадрату) по модулю . Якщо результат за модулем дорівнює −1, то є простим, а в іншому випадку — складеним.
Тест базується на наступній теоремі:
Теорема. При n ≥ 1 число Ферма є простим тоді й тільки тоді, коли .
Доведення. Припустимо, що рівність правильна. Тоді умова теореми Люка виконується при , , відповідно, є простим числом. Навпаки, нехай — просте число. Оскільки — парне число, то , відповідно, . Але , тому символ Лежандра рівний −1. Звідси випливає, що 3 не є квадратичним лишком по модулю . Необхідне порівняння випливає з критерію Ейлера.
Варіації та узагальнення Тест Пепіна є частинним випадком тесту Люка.
Число 3 у тесті Пепіна може бути замінено на 5, 6, 7 чи 10 (), які також є первісними коренями за модулем кожного простого числа Ферма.
Відомо, що Пепін представив критерій з числом 5, а не з числом 3. Прот и Люка відзначили, що також можна застосувати число 3.
Складність обчислень Оскільки тест Пепіна вимагає піднесень до квадрату за модулем , то він виконується за поліноміальний час від довжини числа . Проте, якщо на вхід подається лише число n, то тест Пепіна виконується за над-експоненційний час від довжини входу ().
Історія Через великий розмір чисел Ферма, тест Пепіна був застосований лише 8 разів (для чисел Ферма, чия простота ще не була доведена чи спростована)Conjecture 4. Fermat primes are finite — Pepin tests story, according to Leonid DurmanWilfrid Keller: Fermat factoring status R. M. Robinson (1954): Mersenne and Fermat numbers. 2003 року, після тестування двадцять четвертого числа Ферма (), Майер, Пападопулос і Крендалл висунули припущення, що мине декілька десятків років, перш ніж технології дозволять виконати тести Пепіна для ще недосліджених чисел Ферма, бо їх розміри надто великіRichard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003), The twenty-fourth Fermat number is composite. На листопад 2014 року найменшим неперевіреним числом Ферма було , яке містить десяткових цифр. На стандартному обладнанні тест Пепіна для перевірки такого числа потребує тисячі років. На даний момент гостро
Рік Дослідники Числа Ферма Результати тесту Пепіна Чи знайдений дільник? 1905 Джеймс С. Морхед і Альфред Вестерн складене Так (1970) 1909 Джеймс С. Морхед і Альфред Вестерн складене Так (1980) 1952 Рафаель М. Робінсон складене Так (1953) 1960 Г. А. Паксон складене Так (1974) 1961 Джон Селфрідж і Олександр Гурвіц складене Так (2010) 1987 Дункан Бьюел і Джеффрі Янг Jeff Young & Duncan A. Buell (1988): The twentieth Fermat number is composite, 261—263. складене Ні 1993 Річард Крендалл, Дж. Діньяс, С. Норрі і Джеффрі Янг R. Crandall, J. Doenias, C. Norrie, and J. Young (1995): The twenty-second Fermat number is composite, 863—868. складене Так (2010) 1999 Ернст В. Майер, Джейсон С. Пападопулос і Річард Крендалл складене Ні
Примітки
Література