Просмотр кода страницы Тест Пепина

{| class="standard" align="right" style="margin-left: 1em"
|--
|
[[Псевдокод (язык описания алгоритмов)|Псевдокод]]
: <math>b\,\leftarrow\, 3</math>
: ОТ <math>i=1</math> ДО <math>2^n-1</math> ВЫП <math>b\,\leftarrow\, b^2\bmod{F_n}</math>
: ЕСЛИ <math>b\equiv -1\pmod{F_n}</math> ТО
:: ВОЗВРАТ «<math>F_n</math> — простое»
: ИНАЧЕ
:: ВОЗВРАТ «<math>F_n</math> — составное»
|}

'''Тест Пепина''' — [[тест простоты]] для [[число Ферма|чисел Ферма]] <math>F_n.</math><!-- так как это число будет использоваться в разделе "Описание" --> Тест назван в честь французского математика {{нп5|Пепин, Феофил|Феофила Пепина||Théophile Pépin}}.

== Описание ==

Число <math>3</math> нужно возвести в степень <math>(F_n - 1)/2 = 2^{2^n-1}</math> (в некоторых алгоритмах это реализуется с помощью серии из <math>2^n-1</math> последовательных возведений в квадрат) по модулю <math>F_n</math>. Если результат [[Сравнение по модулю|сравним по модулю]] <math>F_n</math> с −1, то <math>F_n</math> является простым, а в противном случае — составным.

Это утверждение представляет собой следующую теорему:

'''Теорема'''. ''При'' {{Число|''n ≥ 1''}}''число Ферма <math>F_n = 2^{2^n}+1</math> является простым тогда и только тогда, когда <math>3^{(F_n-1)/2}\equiv-1\pmod{F_n}</math>.''

{{Доказ1|Предположим, что сравнение верно. Тогда условие [[Тест простоты Люка|теоремы Люка]] выполняется при <math>n = F_n</math>, <math>a = 3</math>, следовательно, <math>F_n</math> является простым числом. Обратно, пусть <math>F_n</math> — простое число. Так как <math>2^n</math> — четное число, то <math>2^{2^n}\equiv1\pmod{3}</math>, следовательно, <math>F_n\equiv2\pmod{3}</math>. Но <math>F_n\equiv1\pmod{4}</math>, поэтому [[символ Лежандра]] <math>\left(\frac3{F_n}\right)</math> равен −1. Следовательно, 3 не является квадратичным вычетом по модулю <math>F_n</math>. Необходимое сравнение следует из [[Критерий Эйлера|критерия Эйлера]].}}

== Вариации и обобщения ==
Тест Пепина является частным случаем [[Тест простоты Люка|теста Люка]].

Число 3 в тесте Пепина может быть заменено на 5, 6, 7 или 10 ({{OEIS|A129802}}), которые также являются [[Первообразный корень (теория чисел)|первообразными корнями]] по модулю каждого простого числа Ферма.

Известно, что Пепин привёл критерий с числом 5 вместо числа 3. Прот и Люка отметили, что можно также использовать число 3.

== Вычислительная сложность ==
Так как тест Пепина требует <math>2^n-1</math> возведений в квадрат по модулю <math>F_n</math>, то он выполняется за время, имеющее [[полиномиальный алгоритм|полиномиальную зависимость]] от длины числа <math>F_n,</math> но [[экспоненциальный алгоритм|сверхэкспоненциальную]] относительно длины числа ''n'' (<math>\log n</math>).

== История ==
Из-за большого размера чисел Ферма, тест Пепина был использован лишь 8 раз (на числах Ферма, чья простота ещё не была доказана или опровергнута)<ref>[http://www.primepuzzles.net/conjectures/conj_004.htm Conjecture 4. Fermat primes are finite — Pepin tests story, according to Leonid Durman] {{Wayback|url=http://www.primepuzzles.net/conjectures/conj_004.htm |date=20150924081727 }}{{ref-en}}</ref><ref>Wilfrid Keller: [http://www.prothsearch.net/fermat.html Fermat factoring status] {{webarchive|url=https://web.archive.org/web/20160210152415/http://www.prothsearch.net/fermat.html |date=2016-02-10 }}{{ref-en}}</ref><ref>R. M. Robinson (1954): [http://primes.utm.edu/mersenne/LukeMirror/lit/lit_024s.htm Mersenne and Fermat numbers] {{Wayback|url=http://primes.utm.edu/mersenne/LukeMirror/lit/lit_024s.htm |date=20150126092816 }}{{ref-en}}</ref>. Майер, Пападопулос и [[Ричард Крэндалл|Крэндалл]] даже предположили, что, чтобы выполнить тесты Пепина на дальнейшних числах Ферма, понадобится несколько десятилетий, поскольку размеры ещё не исследованных чисел Ферма очень велики<ref>Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003), [http://www.ams.org/journals/mcom/2003-72-243/S0025-5718-02-01479-5/S0025-5718-02-01479-5.pdf The twenty-fourth Fermat number is composite] {{Wayback|url=http://www.ams.org/journals/mcom/2003-72-243/S0025-5718-02-01479-5/S0025-5718-02-01479-5.pdf |date=20141008214703 }}{{ref-en}}</ref>. По состоянию {{На|2023}} наименьшим непроверенным числом Ферма является <math>F_{33}</math>, которое содержит {{formatnum:2585827973}} десятичных цифр. На стандартном оборудовании потребуются тысячи лет, чтобы тест Пепина проверил такое число, и для работы со столь огромными числами Ферма возникает острая нужда в новых алгоритмах.

{| class="wikitable" border="1"
|-
! Год
! Исследователи
! Число Ферма
! Результат теста Пепина
! Удалось ли найти делитель?
|-
| 1905
| Джеймс С. Морхед и Альфред Вестерн
| <math>F_{7}</math>
| составное
| Да (1970)
|-
| 1909
| Джеймс С. Морхед и Альфред Вестерн
| <math>F_{8}</math>
| составное
| Да (1980)
|-
| 1952
| Рафаэль М. Робинсон
| <math>F_{10}</math>
| составное
| Да (1953)
|-
| 1960
| Г. А. Паксон
| <math>F_{13}</math>
| составное
| Да (1974)
|-
| 1961
| Джон Селфридж и Александр Гурвиц
| <math>F_{14}</math>
| составное
| Да (2010)
|-
| 1987
| Дункан Бьюэл и Джеффри Янг
| <math>F_{20}</math><ref>Jeff Young & Duncan A. Buell (1988): [http://www.ams.org/journals/mcom/1988-50-181/S0025-5718-1988-0917833-8/S0025-5718-1988-0917833-8.pdf The twentieth Fermat number is composite] {{Wayback|url=http://www.ams.org/journals/mcom/1988-50-181/S0025-5718-1988-0917833-8/S0025-5718-1988-0917833-8.pdf |date=20140904200304 }}, 261—263.{{ref-en}}</ref>
| составное
| Нет
|-
| 1993
| Ричард Крэндалл, Дж. Диньяс, С. Норри и Джеффри Янг
| <math>F_{22}</math><ref>R. Crandall, J. Doenias, C. Norrie, and J. Young (1995): [http://www.ams.org/journals/mcom/1995-64-210/S0025-5718-1995-1277765-9/S0025-5718-1995-1277765-9.pdf The twenty-second Fermat number is composite] {{Wayback|url=http://www.ams.org/journals/mcom/1995-64-210/S0025-5718-1995-1277765-9/S0025-5718-1995-1277765-9.pdf |date=20141129121129 }}, 863—868.{{ref-en}}</ref>
| составное
| Да (2010)
|-
| 1999
| Эрнст В. Майер, Джейсон С. Пападопулос и Ричард Крэндалл
| <math>F_{24}</math>
| составное
| Нет
|-
|}

== Примечания ==
{{примечания}}

== Литература ==
{{Викиучебник|Программные реализации теста Пепина|Программные реализации теста Пепина}}
* {{статья |автор=P. Pépin |заглавие=Sur la formule <math>2^{2^n}+1</math> |издание=Comptes Rendus Acad. Sci. Paris |номер=85 |год=1877 |страницы=329—333}}
* {{книга |автор=Крэндалл Р., Померанс К. |заглавие=Простые числа |ссылка=https://archive.org/details/isbn_9785453000166|год=2011 |страницы=[https://archive.org/details/isbn_9785453000166/page/n198 198]—200}}

{{Теоретико-числовые алгоритмы}}

[[Категория:Тесты простоты]]