Тест Пепіна

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

Псевдокод

ВІД ДО ВИКОН
ЯКЩО ТО
ПОВЕРНЕННЯ « — просте»
ІНАКШЕ
ПОВЕРНЕННЯ « — складене»

Опис тесту

Тест Пепіна полягає в піднесенні числа до степені ( послідовних піднесень до квадрату) по модулю . Якщо результат за модулем дорівнює −1, то є простим, а в іншому випадку — складеним.

Тест базується на наступній теоремі:

Теорема. При n ≥ 1 число Ферма є простим тоді й тільки тоді, коли .

Доведення. Припустимо, що рівність правильна. Тоді умова теореми Люка виконується при , , відповідно, є простим числом. Навпаки, нехай  — просте число. Оскільки  — парне число, то , відповідно, . Але , тому символ Лежандра рівний −1. Звідси випливає, що 3 не є квадратичним лишком по модулю . Необхідне порівняння випливає з критерію Ейлера.

Варіації та узагальнення

Тест Пепіна є частинним випадком тесту Люка.

Число 3 у тесті Пепіна може бути замінено на 5, 6, 7 чи 10 (послідовність A129802 з Онлайн енциклопедії послідовностей цілих чисел, OEIS), які також є первісними коренями за модулем кожного простого числа Ферма.

Відомо, що Пепін представив критерій з числом 5, а не з числом 3. Прот и Люка відзначили, що також можна застосувати число 3.

Складність обчислень

Оскільки тест Пепіна вимагає піднесень до квадрату за модулем , то він виконується за поліноміальний час від довжини числа . Проте, якщо на вхід подається лише число n, то тест Пепіна виконується за над-експоненційний час від довжини входу ().

Історія

Через великий розмір чисел Ферма, тест Пепіна був застосований лише 8 разів (для чисел Ферма, чия простота ще не була доведена чи спростована)[1][2][3]. 2003 року, після тестування двадцять четвертого числа Ферма (), Майер, Пападопулос і Крендалл висунули припущення, що мине декілька десятків років, перш ніж технології дозволять виконати тести Пепіна для ще недосліджених чисел Ферма, бо їх розміри надто великі[4]. На листопад 2014 року найменшим неперевіреним числом Ферма було , яке містить 2 585 827 973 десяткових цифр. На стандартному обладнанні тест Пепіна для перевірки такого числа потребує тисячі років. На даний момент[коли?] гостро[ненейтрально] необхідні нові алгоритми для роботи з настільки величезними числами.[джерело?]

Рік Дослідники Числа Ферма Результати тесту Пепіна Чи знайдений дільник?
1905 Джеймс С. Морхед і Альфред Вестерн складене Так (1970)
1909 Джеймс С. Морхед і Альфред Вестерн складене Так (1980)
1952 Рафаель М. Робінсон складене Так (1953)
1960 Г. А. Паксон складене Так (1974)
1961 Джон Селфрідж і Олександр Гурвіц складене Так (2010)
1987 Дункан Бьюел і Джеффрі Янг [5] складене Ні
1993 Річард Крендалл, Дж. Діньяс, С. Норрі і Джеффрі Янг [6] складене Так (2010)
1999 Ернст В. Майер, Джейсон С. Пападопулос і Річард Крендалл складене Ні

Примітки

  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 . — Comptes Rendus Acad. Sci. Paris, 1877. № 85.
  • Крэндалл Р., Померанс К. . Простые числа. — 2011. — С. 198—200.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.