Тест Люка Лемера

Тест Люка — Лемера — полиномиальный, детерминированный и безусловный (то есть не зависящий от недоказанных гипотез) тест простоты для чисел Мерсенна. Сформулирован Эдуардом Люка в 1878 году и доказан Лемером в 1930 году.
 При заданном простом числе p>2 тест позволяет за полиномиальное время от битовой длины p числа Мерсенна Mp=2p1 определить, является Mp простым или составным. Доказательство справедливости теста существенно опирается на функции Люка, что позволило обобщить тест Люка — Лемера на некоторые числа, вид которых отличен от чисел Мерсенна.
 Благодаря этому тесту самыми большими известными простыми числами почти всегда были простые числа Мерсенна, причём даже до появления компьютеров; именно он лежит в основе проекта распределённых вычислений GIMPS, занимающегося поиском новых простых чисел Мерсенна. Также он интересен своей связью с чётными совершенными числами.

Формулировка


 Тест основывается на следующем критерии простоты чисел Мерсенна:
 Для проверки простоты Mp последовательность чисел S1,S2,,Sp1 вычисляется по модулю числа Mp (то есть вычисляются не сами числа Sk, длина которых растёт экспоненциально, а остатки от деления Sk на Mp, длина которых ограничена p битами). Последнее число в этой последовательности Sp1modMp называется вычетом Люка — Лемера. Таким образом, число Мерсенна Mp является простым тогда и только тогда, когда число p — нечётное простое и вычет Люка — Лемера равен нулю. Сам алгоритм можно записать в виде псевдокода:
\textttLucas–Lehmer\texttt(p)\\\texttt    ►Вход: простое нечётное число p\\\texttt    S = 4\\\texttt    k = 1\\\texttt    M = 2\textttp\texttt − 1\\\texttt    \textttДо \textttтех \textttпока\texttt k != p - 1 \textttвыполнять\\\texttt        S = ((S × S) − 2) mod M\\\texttt        k += 1\\\texttt    \textttКонец \textttцикла\\\texttt    \textttЕсли\texttt S = 0 \textttвыполнять\\\texttt        \textttВозвратить\texttt ПРОСТОЕ\\\texttt    \textttиначе\\\texttt        \textttВозвратить\texttt СОСТАВНОЕ\\\texttt    \textttКонец \textttусловия
 Возможными значениями S1 являются: 4,10,52,724,970,10084, .
 Не обязательно проверять все простые нечётные p при непосредственном переборе чисел Мерсенна, что следует, например, из следующей доказанной Эйлером теоремы:

Доказательство


 Один из подходов к доказательству основан на использовании функций Люка:

Vn(P,Q)=αn+βn,


Un(P,Q)=αnβnαβ,
  где α,β — корни квадратного уравнения

x2Px+Q=0
  с дискриминантом D=P24Q, причём P и Q взаимно просты.
 В частности, при доказательстве используются некоторые свойства этих функций, а именно:

  1. Vn2DUn2=4Qn


 2. V2n=Vn22Qn,U2n=UnVn


 3. Vn+DUn2=(P+D2)n


 4. Если PP(modN), QQ(modN), (Q,N)=1 и


QP=P22Q(modN),


 то


 \{begin\{cases\}Q\^nV\_n(P',1)\{equiv V\_\{2n\}(P,Q)\{pmod N
  \{\{ PQ\^\{n-1\}U\_n(P',1)\{equiv U\_\{2n\}(P,Q)\{pmod N\{end\{cases\}

  5. Если p — простое, такое, что 2DQ взаимно просто с p, то p делит нацело UΦ(p)(P,Q),


 где Φ(p)=p(Dp), а (Dp) — символ Лежандра.
  Схема доказательства:

Необходимость


 Из свойства 4. по модулю N=Mp при P=2, Q=2, следует:

2nVn(4,1)V2n(2,2)(modN),
  а по свойству 2.

V2n(4,1)=Vn2(4,1)2,
  поэтому

Sp1VN+14(4,1)(modN)
  и

VN+12(2,2)2N+14Sp1(modN)
D=224(2)=12, поэтому если N — простое, то (DN)=1 и из последних двух свойств N делит

UN+1(2,2)=VN+12(2,2)UN+12(2,2)
  Далее, из свойств 1. и 2.

VN+1=VN+1222(2)N+128+4=12(modN),
  но по свойству 3.

VN+12(1+3)N+1=2(1+3)(1+3N1232(13)=4(modN),
  то есть N делит VN+12(2,2), а значит и Sp1.

Достаточность


 Если N делит Sp1, то из доказательства необходимости следует, что оно делит и VN+12. N взаимно просто с UN+12 по свойству 1., а по свойству 2. — делит UN+1. Но тогда каждый простой делитель числа N представим в виде ±1+k2p>N, то есть N=Mp — простое.

История


 Критерий простоты был предложен французским математиком Люка в 1878 году. В частности, Люка показал, что алгоритм позволяет проверять простоту Mp для простых p1(mod4). В 1930 году американский математик Лемер полностью доказал справедливость критерия для всех простых нечётных p в своей диссертации на соискание учёной степени доктора философии.
 В 1952 году Робинсон при поддержке Лемера провел вычисления на компьютере SWAC с использованием теста Люка — Лемера, результатом которого стало открытие простых чисел M521 и M607. Позднее в этом же году были открыты M1279, M2203 и M2281.
 Лёгкость реализации теста и рост вычислительных мощностей компьютеров позволили фактически любому человеку заниматься поиском простых чисел Мерсенна. Так, в 1978 году два американских старшеклассника Лора Никель и Курт Нолл (Лемер преподавал им теорию чисел) за 3 года работы доказали простоту числа M21701, используя суперкомпьютер CDC Cyber 176 в Калифорнийском университете.
 Наибольшее из известных простых чисел Мерсенна на 2016 год, полученное с помощью теста Люка — Лемера, это M74207281.

Примеры


 Требование нечётности p в условии критерия существенно, так как M2=221=3 — простое, но S14(mod3)=10.
 Число M13=2131=8191 — простое. Действительно,

S1=4
S2422(mod8191)=14
S31422(mod8191)=194
S419422(mod8191)=4870
S5487022(mod8191)=3953
S6395322(mod8191)=5970
S7597022(mod8191)=1857
S8185722(mod8191)=36
S93622(mod8191)=1294
S10129422(mod8191)=3470
S11347022(mod8191)=128
S1212822(mod8191)=0
  Применение теста к числу M11=2111=2047 показывает, что оно составное:

S1=4
S2422(mod2047)=14
S31422(mod2047)=194
S419422(mod2047)=788
S578822(mod2047)=701
S670122(mod2047)=119
S711922(mod2047)=1877
S8187722(mod2047)=240
S924022(mod2047)=282
S1028222(mod2047)=17360
  Действительно, 2047=2389.

Вычислительная сложность


 В рассматриваемом тесте две основные операции: возведение в квадрат и деление по модулю. Эффективный алгоритм деления по модулю числа Мерсенна на компьютере (фактически сводящийся к нескольким операциям битового сдвига) дает следующая теорема:
 Например, чтобы вычислить остаток от деления числа x=916 на M5=251=31, нужно исходное число преобразовать в двоичный вид: 916=11100101002, и, согласно теореме, разбивать x на две части каждый раз, когда оно превосходит M5:

916mod251(916mod25)+91625(mod251)101002+111002(mod251)1100002(mod251)100002+12(mod251)100012(mod251)=100012=17
  При использовании этого способа деления по модулю вычислительная сложность теста будет определяться сложностью алгоритма возведения в квадрат. Длина Mp составляет p бит, а алгоритм умножения двух чисел, например, «в столбик», имеет сложность O(p2). Так как возведение в квадрат в тесте происходит O(p) раз, то вычислительная сложность алгоритма равна O(p3). Тест можно ускорить, если использовать алгоритмы быстрого умножения больших целых чисел, например, метод умножения Шёнхаге — Штрассена. Сложность теста в таком случае составит O(p2lnplnlnp).

Вариации и обобщения


 Условие в тесте можно ослабить и потребовать лишь, чтобы Sp2±2p+12(modMp), откуда немедленно следует:

Sp1=2p+12=2(2p1)0(modMp).
  В 1930 году Лемер вывел критерий простоты для чисел вида k2n1, где k<2n, а в 1969 году модифицировал тест Люка — Лемера для чисел такого вида, который впоследствии был дополнен Стечкиным. Возможно обобщение теста и на числа вида A22n+B2n1.
 были доказаны критерии простоты, аналогичные тесту Люка — Лемера, для чисел вида k3n1(k<3n) и k2n3m1,(k<2n3m), а также для некоторых чисел вида kqn1, где q>3 — простое $(k Существует более общий (N21)-тест простоты, который применим для любого натурального числа N, если известно полное или частичное разложение на простые множители числа N1 или N+1.

Применения


 Благодаря тесту Люка — Лемера, простые числа Мерсенна удерживают лидерство как самые большие известные простые числа, хотя и до существования теста числа Мерсенна почти всегда были наибольшими простыми. Так, в 1588 году была доказана простота чисел M17 и M19.
 Евклид доказал, что всякое число вида 2p1(2p1)=2p1Mp — совершенное, если Mp — простое, а Эйлер показал, что все чётные совершенные числа имеют такой вид; поэтому тест Люка — Лемера фактически позволяет найти все чётные совершенные числа.
 Именно этот тест лежит в основе проекта распределённых вычислений GIMPS, занимающегося поиском новых простых чисел Мерсенна, хотя до сих пор не доказано, что их бесконечно много.
 Также данный тест используется для тестирования аппаратного обеспечения. Так, в 1992 году специалисты компании протестировали новый суперкомпьютер компании Cray, используя программу, написанную для поиска простых чисел Мерсенна. В результате за 19 часов работы программы было открыто простое число M756839.