Processing math: 100%

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

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


 2. V2n=V2n2Qn,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)\{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Φ(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)=V2n(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=V2N+122(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.