В математике , тест пепин является тестом на простоту , который может быть использован для определения , является ли число Ферма является премьером . Это вариант теста Прота . Тест назван в честь французского математика Теофиля Пепена .
Описание теста
Позволять - n- е число Ферма. Тест Пепина утверждает, что при n > 0
- простое тогда и только тогда, когда
Выражение можно оценить по модулю путем повторного возведения в квадрат . Это делает тест быстрым алгоритмом с полиномиальным временем . Однако числа Ферма растут так быстро, что лишь небольшую часть чисел Ферма можно проверить в разумные сроки и в разумных пределах.
Другие базы могут использоваться вместо 3, эти базы
- 3, 5, 6, 7, 10, 12, 14, 20, 24, 27, 28, 39, 40, 41, 45, 48, 51, 54, 56, 63, 65, 75, 78, 80, 82, 85, 90, 91, 96, 102, 105, 108, 112, 119, 125, 126, 130, 147, 150, 156, 160, ... (последовательность A129802 в OEIS ).
Простые числа в приведенной выше последовательности называются элитными простыми числами , они
- 3, 5, 7, 41, 15361, 23041, 26881, 61441, 87041, 163841, 544001, 604801, 6684673, 14172161, 159318017, 446960641, 1151139841, 3208642561, 38126223361, 108905103361, 3117279402881, 17172794012801, 1717274840288 . (последовательность A102742 в OEIS )
Для целого числа b > 1 база b может использоваться тогда и только тогда, когда только конечное число чисел Ферма F n удовлетворяет тому, что, где - символ Якоби .
Фактически, тест Пепина такой же, как тест Эйлера-Якоби для чисел Ферма, поскольку символ Якоби равно −1, т. е. нет чисел Ферма, которые являются псевдопростыми числами Эйлера-Якоби для этих базисов, перечисленных выше.
Доказательство правильности
Достаточность: предположим, что сравнение
держит. потом, таким образом, мультипликативный порядок 3 по модулю разделяет , что является степенью двойки. С другой стороны, порядок не делит, а значит, он должен быть равен . В частности, есть не менее числа ниже взаимно проста с , а это может произойти, только если простое.
Необходимость: предположим, чтопростое. По критерию Эйлера ,
- ,
где - символ Лежандра . Повторным возведением в квадрат мы находим, что, таким образом , а также . В виде, мы приходим к выводу из закона квадратичной взаимности .
Исторические тесты Пепена
Из-за разреженности чисел Ферма тест Пепина запускался только восемь раз (на числах Ферма, статусы простоты которых еще не были известны). [1] [2] [3] Майер, Пападопулос и Крэндалл предполагают, что на самом деле, из-за размера еще не определенных чисел Ферма, потребуется значительный прогресс в технологии, прежде чем какие-либо тесты Пепина можно будет запустить в разумном количестве время. [4] По состоянию на 2016 год[Обновить] наименьшее непроверенное число Ферма без известного простого множителя который состоит из 2 585 827 973 цифр.
Год | Пруверы | Число Ферма | Результат теста Пепина | Фактор найден позже? |
---|---|---|---|---|
1905 г. | Морхед и Вестерн | составной | Да (1970) | |
1909 г. | Морхед и Вестерн | составной | Да (1980) | |
1952 г. | Робинсон | составной | Да (1953) | |
1960 г. | Паксон | составной | Да (1974) | |
1961 г. | Селфридж и Гурвиц | составной | Да (2010) | |
1987 г. | Buell & Young | составной | Нет | |
1993 г. | Крэндалл , Дениас, Норри и Янг | составной | Да (2010) | |
1999 г. | Майер, Пападопулос и Крэндалл | составной | Нет |
Заметки
- ^ Гипотеза 4. Простые числа Ферма конечны - история тестов Пепина, по словам Леонида Дурмана.
- ^ Уилфрид Келлер: Статус факторинга Fermat
- ^ Р. М. Робинсон (1954): числа Мерсенна и Ферма
- ^ Ричард Э. Крэндалл, Эрнст В. Майер и Джейсон С. Пападопулос, Двадцать четвертое число Ферма является составным (2003)
Рекомендации
- П. Пепен, Sur la Formule, Comptes rendus de l'Académie des Sciences de Paris 85 (1877), стр. 329–333.