Loading [MathJax]/extensions/TeX/mathchoice.js

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

Тест Люка — Лемера — полиномиальный, детерминированный ибезусловный (то есть не зависящий от недоказанных гипотез) тест простотыдля чисел Мерсенна. Сформулирован Эдуардом Люка в 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\textsuperscript\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. V2nDU2n=4Qn


 2. V2n=V2n2Qn,U2n=UnVn


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


 4. Если P'\equiv P \pmod N, Q'\equiv Q \pmod N, (Q,N)=1 и


QP'=P^2-2Q \pmod N,


 то


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

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


 где \Phi(p)=p-\left(\frac{D}{p}\right), а \left(\frac{D}{p}\right)— символ Лежандра.
 Схема доказательства:

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


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

2^nV_n(-4, 1)\equiv V_{2n}(2, -2)\pmod N,
 а по свойству 2.

V_{2n}(-4, 1)=V_n^2(-4, 1)-2,
 поэтому

S_{p-1}\equiv V_{\frac{N+1}{4}}(-4,1)\pmod N
 и

V_{\frac{N+1}{2}}(2,-2)\equiv 2^\frac{N+1}{4}S_{p-1}\pmod N
D=2^2-4\cdot(-2)=12, поэтому если N — простое, то\left(\frac{D}{N}\right)=-1 и из последних двух свойств N делит

U_{N+1}(2,-2)=V_{\frac{N+1}{2}}(2,-2)U_{\frac{N+1}{2}}(2,-2)
 Далее, из свойств 1. и 2.

V_{N+1}=V_{\frac{N+1}{2}}^2-2\cdot(-2)^\frac{N+1}{2}\equiv 8+4=12\pmod N,
 но по свойству 3.

V_{N+1}\equiv 2(1+\sqrt{3})^{N+1}=2(1+\sqrt{3})(1+3^\frac{N-1}{2}\sqrt{3}\equiv 2(1-3)=-4\pmod N,
 то есть N делит V_{\frac{N+1}{2}}(2,-2), а значит и S_{p-1}.

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


 Если N делит S_{p-1}, то из доказательства необходимости следует,что оно делит и V_{\frac{N+1}{2}}. N взаимно просто сU_{\frac{N+1}{2}} по свойству 1., а по свойству 2. — делитU_{N+1}. Но тогда каждый простой делитель числа N представим в виде\pm 1 + k2^p>\sqrt{N}, то есть N=M_p — простое.

История


 Критерий простоты был предложен французским математиком Люка в 1878году. В частности, Люка показал, что алгоритм позволяет проверятьпростоту M_p для простых p\equiv 1 \pmod 4. В 1930 году американскийматематик Лемер полностью доказал справедливость критерия для всехпростых нечётных p в своей диссертации на соискание учёной степенидоктора философии.
 В 1952 году Робинсон при поддержке Лемера провел вычисления накомпьютере SWAC с использованием теста Люка — Лемера, результатомкоторого стало открытие простых чисел M_{521} и M_{607}. Позднее вэтом же году были открыты M_{1279}, M_{2203} и M_{2281}.
 Лёгкость реализации теста и рост вычислительных мощностей компьютеровпозволили фактически любому человеку заниматься поиском простых чиселМерсенна. Так, в 1978 году два американских старшеклассника Лора Никельи Курт Нолл (Лемер преподавал им теорию чисел) за 3 года работы доказалипростоту числа M_{21701}, используя суперкомпьютер CDC Cyber 176 вКалифорнийском университете.
 Наибольшее из известных простых чисел Мерсенна на 2016 год, полученное спомощью теста Люка — Лемера, это M_{74207281}.

Примеры


 Требование нечётности p в условии критерия существенно, так какM_2=2^2-1=3 — простое, но S_1\equiv 4 \pmod 3 = 1\not=0.
 Число M_{13} = 2^{13} - 1 = 8191 — простое. Действительно,

S_1=4
S_2\equiv 4^2-2\pmod {8191} = 14
S_3\equiv 14^2-2\pmod {8191}=194
S_4\equiv194^2-2\pmod {8191}=4870
S_5\equiv4870^2-2\pmod {8191}=3953
S_6\equiv3953^2-2\pmod {8191}=5970
S_7\equiv5970^2-2\pmod {8191}=1857
S_8\equiv1857^2-2\pmod {8191}=36
S_9\equiv36^2-2\pmod {8191}=1294
S_{10}\equiv1294^2-2\pmod {8191}=3470
S_{11}\equiv3470^2-2\pmod {8191}=128
S_{12}\equiv128^2-2\pmod {8191}=0
 Применение теста к числу M_{11}=2^{11}-1=2047 показывает, что оносоставное:

S_1=4
S_2\equiv 4^2-2\pmod {2047} = 14
S_3\equiv 14^2-2\pmod {2047}=194
S_4\equiv194^2-2\pmod {2047}=788
S_5\equiv788^2-2\pmod {2047}=701
S_6\equiv701^2-2\pmod {2047}=119
S_7\equiv119^2-2\pmod {2047}=1877
S_8\equiv1877^2-2\pmod {2047}=240
S_9\equiv240^2-2\pmod {2047}=282
S_{10}\equiv282^2-2\pmod {2047}=1736\not=0
 Действительно, 2047=23\cdot 89.

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


 В рассматриваемом тесте две основные операции: возведение в квадрат иделение по модулю. Эффективный алгоритм деления по модулю числа Мерсеннана компьютере (фактически сводящийся к нескольким операциям битовогосдвига) дает следующая теорема:
 Например, чтобы вычислить остаток от деления числа x=916 наM_5=2^5-1=31, нужно исходное число преобразовать в двоичный вид:916 = {1110010100}_2, и, согласно теореме, разбивать x на две частикаждый раз, когда оно превосходит M_5:

\begin{aligned}916 \bmod 2^5-1 &\equiv\left(916\bmod 2^5\right) + \left\lfloor \frac{916}{2^5}\right\rfloor\pmod {2^5-1}\\&\equiv{10100}_2+{11100}_2\pmod {2^5-1}\\&\equiv {110000}_2\pmod {2^5-1}\\&\equiv{10000}_2+1_2\pmod{2^5-1}\\&\equiv {10001}_2\pmod{2^5-1}\\&={10001}_2\\&=17\end{aligned}
 При использовании этого способа деления по модулю вычислительнаясложность теста будет определяться сложностью алгоритма возведения вквадрат. Длина M_p составляет p бит, а алгоритм умножения двухчисел, например, «в столбик», имеет сложность O(p^2). Так каквозведение в квадрат в тесте происходит O(p) раз, то вычислительнаясложность алгоритма равна O(p^3). Тест можно ускорить, еслииспользовать алгоритмы быстрого умножения больших целых чисел, например,метод умножения Шёнхаге — Штрассена. Сложность теста в таком случаесоставит O(p^{2}\ln{p}\ln{\ln{p}}).

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


 Условие в тесте можно ослабить и потребовать лишь, чтобыS_{p-2}\equiv \pm 2^{\frac{p+1}{2}} \pmod {M_p}, откуда немедленноследует:

S_{p-1}=2^{p+1}-2=2(2^p-1) \equiv 0 \pmod {M_p}.
 В 1930 году Лемер вывел критерий простоты для чисел вида k2^n-1, гдеk<2^n, а в 1969 году модифицировал тест Люка — Лемера для чиселтакого вида, который впоследствии был дополнен Стечкиным. Возможнообобщение теста и на числа вида A2^{2n}+B2^{n}-1.
 были доказаны критерии простоты, аналогичные тесту Люка — Лемера, длячисел вида k3^n-1\;(k<3^n) и k2^n3^m-1,\;(k<2^n3^m), а также длянекоторых чисел вида kq^n-1, где q>3 — простое $(k Существует более общий (N^2-1)-тест простоты, который применим длялюбого натурального числа N, если известно полное или частичноеразложение на простые множители числа N-1 или N+1.

Применения


 Благодаря тесту Люка — Лемера, простые числа Мерсенна удерживаютлидерство как самые большие известные простые числа, хотя и досуществования теста числа Мерсенна почти всегда были наибольшимипростыми. Так, в 1588 году была доказана простота чисел M_{17} иM_{19}.
 Евклид доказал, что всякое число вида 2^{p-1}(2^p-1)=2^{p-1}M_p —совершенное, если M_p — простое, а Эйлер показал, что все чётныесовершенные числа имеют такой вид; поэтому тест Люка — Лемерафактически позволяет найти все чётные совершенные числа.
 Именно этот тест лежит в основе проекта распределённых вычислений GIMPS,занимающегося поиском новых простых чисел Мерсенна, хотя до сих пор недоказано, что их бесконечно много.
 Также данный тест используется для тестирования аппаратного обеспечения.Так, в 1992 году специалисты компании протестировали новыйсуперкомпьютер компании Cray, используя программу, написанную для поискапростых чисел Мерсенна. В результате за 19 часов работы программы былооткрыто простое число M_{756839}.