Те́ст Люка́ — Ле́мера ( англ. Lucas-Lehmer test , сокр. LLT ) — полиномиальный , детерминированный и безусловный (то есть не зависящий от недоказанных гипотез) тест простоты для чисел Мерсенна . Сформулирован Эдуардом Люка в 1878 году и доказан Лемером в 1930 году .

При заданном простом числе ${\displaystyle p>2}$ тест позволяет за полиномиальное время от битовой длины ${\displaystyle p}$ числа Мерсенна ${\displaystyle M_{p}=2^{p}-1}$ определить, является ${\displaystyle M_{p}}$ простым или составным . Доказательство справедливости теста существенно опирается на функции Люка , что позволило обобщить тест Люка — Лемера на некоторые числа, вид которых отличен от чисел Мерсенна .

Благодаря этому тесту самыми большими известными простыми числами почти всегда были простые числа Мерсенна, причём даже до появления компьютеров ; именно он лежит в основе проекта распределённых вычислений GIMPS , занимающегося поиском новых простых чисел Мерсенна. Также он интересен своей связью с чётными совершенными числами .

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

Тест основывается на следующем критерии простоты чисел Мерсенна :

Пусть ${\displaystyle p}$ — простое нечётное. Число Мерсенна ${\displaystyle M_{p}=2^{p}-1}$ простое тогда и только тогда, когда оно делит нацело ${\displaystyle (p-1)}$ -й член последовательности

${\displaystyle 4,\;14,\;194,\;37634,\;\ldots }$ ,

задаваемой рекуррентно : ${\displaystyle S_{k}={\begin{cases}4&k=1,\\S_{k-1}^{2}-2&k>1.\end{cases}}}$

Лемер , 1930 год

Для проверки простоты ${\displaystyle M_{p}}$ последовательность чисел ${\displaystyle S_{1},S_{2},\ldots ,S_{p-1}}$ вычисляется по модулю числа ${\displaystyle M_{p}}$ (то есть вычисляются не сами числа ${\displaystyle S_{k}}$ , длина которых растёт экспоненциально , а остатки от деления ${\displaystyle S_{k}}$ на ${\displaystyle M_{p}}$ , длина которых ограничена ${\displaystyle p}$ битами ). Последнее число в этой последовательности ${\displaystyle S_{p-1}{\bmod {M}}_{p}}$ называется вычетом Люка — Лемера . Таким образом, число Мерсенна ${\displaystyle M_{p}}$ является простым тогда и только тогда, когда число ${\displaystyle p}$ — нечётное простое и вычет Люка — Лемера равен нулю. Сам алгоритм можно записать в виде псевдокода :

LLT(p)
    ►Вход: простое нечётное число p
    S = 4
    k = 1
    M = 2p − 1
    До тех пока k != p - 1 выполнять
        S = ((S × S) − 2) mod M
        k += 1
    Конец цикла
    Если S = 0 выполнять
        Возвратить ПРОСТОЕ
    иначе
        Возвратить СОСТАВНОЕ
    Конец условия

Значения ${\displaystyle S_{1}}$ , для которых справедлив критерий простоты, образуют последовательность: ${\displaystyle 4,\;10,\;52,\;724,\;970,\;10084,\;\ldots }$ .

Не обязательно проверять все простые нечётные ${\displaystyle p}$ при непосредственном переборе, поскольку некоторые числа Мерсенна специального вида всегда являются составными, что следует, например, из следующей доказанной Эйлером теоремы :

Если числа ${\displaystyle p=4n+3}$ и ${\displaystyle q=2p+1=8n+7}$ — простые, то ${\displaystyle M_{p}\equiv 0{\pmod {q}}}$ .

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

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

${\displaystyle V_{n}(P,Q)=\alpha ^{n}+\beta ^{n},}$

${\displaystyle U_{n}(P,Q)={\frac {\alpha ^{n}-\beta ^{n}}{\alpha -\beta }},}$

где ${\displaystyle \alpha ,\;\beta }$ — корни квадратного уравнения

${\displaystyle x^{2}-Px+Q=0}$

с дискриминантом ${\displaystyle D=P^{2}-4Q,}$ причём ${\displaystyle P}$ и ${\displaystyle Q}$ взаимно просты .

В частности, при доказательстве используются некоторые свойства этих функций, а именно :

1. ${\displaystyle V_{n}^{2}-DU_{n}^{2}=4Q^{n}}$

2. ${\displaystyle V_{2n}=V_{n}^{2}-2Q^{n},\quad U_{2n}=U_{n}V_{n}}$

3. ${\displaystyle {\frac {V_{n}+{\sqrt {D}}U_{n}}{2}}=\left({\frac {P+{\sqrt {D}}}{2}}\right)^{n}}$

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

${\displaystyle QP'=P^{2}-2Q{\pmod {N}}}$ ,

то

${\displaystyle {\begin{cases}Q^{n}V_{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. Если ${\displaystyle p}$ — простое, такое, что ${\displaystyle 2DQ}$ взаимно просто с ${\displaystyle p}$ , то ${\displaystyle p}$ делит нацело ${\displaystyle U_{\Phi (p)}(P,Q)}$ ,

где ${\displaystyle \Phi (p)=p-\left({\frac {D}{p}}\right)}$ , а ${\displaystyle \left({\frac {D}{p}}\right)}$ — символ Лежандра .

Схема доказательства :

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

Из свойства 4. по модулю ${\displaystyle N=M_{p}}$ при ${\displaystyle P=2}$ , ${\displaystyle Q=-2}$ , следует:

${\displaystyle 2^{n}V_{n}(-4,1)\equiv V_{2n}(2,-2){\pmod {N}}}$ ,

а по свойству 2.

${\displaystyle V_{2n}(-4,1)=V_{n}^{2}(-4,1)-2}$ ,

поэтому

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

и

${\displaystyle V_{\frac {N+1}{2}}(2,-2)\equiv 2^{\frac {N+1}{4}}S_{p-1}{\pmod {N}}}$

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

${\displaystyle U_{N+1}(2,-2)=V_{\frac {N+1}{2}}(2,-2)U_{\frac {N+1}{2}}(2,-2)}$

Далее, из свойств 1. и 2.

${\displaystyle V_{N+1}=V_{\frac {N+1}{2}}^{2}-2\cdot (-2)^{\frac {N+1}{2}}\equiv 8+4=12{\pmod {N}}}$ ,

но по свойству 3.

${\displaystyle 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}}}$ ,

то есть ${\displaystyle N}$ делит ${\displaystyle V_{\frac {N+1}{2}}(2,-2)}$ , а значит и ${\displaystyle S_{p-1}}$ .

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

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

История

Критерий простоты был предложен французским математиком Люка в 1878 году . В частности, Люка показал, что алгоритм позволяет проверять простоту ${\displaystyle M_{p}}$ для простых ${\displaystyle p\equiv 1{\pmod {4}}}$ . В 1930 году американский математик Лемер полностью доказал справедливость критерия для всех простых нечётных ${\displaystyle p}$ в своей диссертации на соискание учёной степени доктора философии .

В 1952 году Робинсон при поддержке Лемера провел вычисления на компьютере SWAC с использованием теста Люка — Лемера, результатом которого стало открытие простых чисел ${\displaystyle M_{521}}$ и ${\displaystyle M_{607}}$ . Позднее в этом же году были открыты ${\displaystyle M_{1279}}$ , ${\displaystyle M_{2203}}$ и ${\displaystyle M_{2281}}$ .

Лёгкость реализации теста и рост вычислительных мощностей компьютеров позволили фактически любому человеку заниматься поиском простых чисел Мерсенна. Так, в 1978 году два американских старшеклассника Лора Никель и Курт Нолл (Лемер преподавал им теорию чисел) за 3 года работы доказали простоту числа ${\displaystyle M_{21701}}$ , используя суперкомпьютер CDC в Калифорнийском университете .

Наибольшее из известных простых чисел Мерсенна на 2018 год, полученное с помощью теста Люка — Лемера, это ${\displaystyle M_{82589933}}$ .

Примеры

Требование нечётности ${\displaystyle p}$ в условии критерия существенно, так как ${\displaystyle M_{2}=2^{2}-1=3}$ — простое , но ${\displaystyle S_{1}\equiv 4{\pmod {3}}=1\not =0}$ .

Число ${\displaystyle M_{13}=2^{13}-1=8191}$ — простое . Действительно,

${\displaystyle S_{1}=4}$

${\displaystyle S_{2}\equiv 4^{2}-2{\pmod {8191}}=14}$

${\displaystyle S_{3}\equiv 14^{2}-2{\pmod {8191}}=194}$

${\displaystyle S_{4}\equiv 194^{2}-2{\pmod {8191}}=4870}$

${\displaystyle S_{5}\equiv 4870^{2}-2{\pmod {8191}}=3953}$

${\displaystyle S_{6}\equiv 3953^{2}-2{\pmod {8191}}=5970}$

${\displaystyle S_{7}\equiv 5970^{2}-2{\pmod {8191}}=1857}$

${\displaystyle S_{8}\equiv 1857^{2}-2{\pmod {8191}}=36}$

${\displaystyle S_{9}\equiv 36^{2}-2{\pmod {8191}}=1294}$

${\displaystyle S_{10}\equiv 1294^{2}-2{\pmod {8191}}=3470}$

${\displaystyle S_{11}\equiv 3470^{2}-2{\pmod {8191}}=128}$

${\displaystyle S_{12}\equiv 128^{2}-2{\pmod {8191}}=0}$

Применение теста к числу ${\displaystyle M_{11}=2^{11}-1=2047}$ показывает, что оно составное :

${\displaystyle S_{1}=4}$

${\displaystyle S_{2}\equiv 4^{2}-2{\pmod {2047}}=14}$

${\displaystyle S_{3}\equiv 14^{2}-2{\pmod {2047}}=194}$

${\displaystyle S_{4}\equiv 194^{2}-2{\pmod {2047}}=788}$

${\displaystyle S_{5}\equiv 788^{2}-2{\pmod {2047}}=701}$

${\displaystyle S_{6}\equiv 701^{2}-2{\pmod {2047}}=119}$

${\displaystyle S_{7}\equiv 119^{2}-2{\pmod {2047}}=1877}$

${\displaystyle S_{8}\equiv 1877^{2}-2{\pmod {2047}}=240}$

${\displaystyle S_{9}\equiv 240^{2}-2{\pmod {2047}}=282}$

${\displaystyle S_{10}\equiv 282^{2}-2{\pmod {2047}}=1736\not =0}$

Действительно, ${\displaystyle 2047=23\cdot 89}$ .

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

В рассматриваемом тесте две основные операции: возведение в квадрат и деление по модулю . Эффективный алгоритм деления по модулю числа Мерсенна на компьютере (фактически сводящийся к нескольким операциям битового сдвига ) дает следующая теорема :

Для целого числа ${\displaystyle x}$ и числа Мерсенна ${\displaystyle M_{p}=2^{p}-1}$ имеет место сравнение по модулю

${\displaystyle x\equiv \left(x{\bmod {2}}^{p}\right)+\left\lfloor {\frac {x}{2^{p}}}\right\rfloor {\pmod {M_{p}}}}$ ,

причём умножение на ${\displaystyle 2^{k}}$ по модулю ${\displaystyle M_{p}}$ равносильно левому циклическому сдвигу на ${\displaystyle k}$ бит (если ${\displaystyle k<0}$ , то сдвиг осуществляется в обратную сторону).

Например, чтобы вычислить остаток от деления числа ${\displaystyle x=916}$ на ${\displaystyle M_{5}=2^{5}-1=31}$ , нужно исходное число преобразовать в двоичный вид: ${\displaystyle 916={1110010100}_{2}}$ , и, согласно теореме, разбивать ${\displaystyle x}$ на две части каждый раз, когда оно превосходит ${\displaystyle M_{5}}$ :

${\displaystyle {\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}}}$

При использовании этого способа деления по модулю вычислительная сложность теста будет определяться сложностью алгоритма возведения в квадрат. Длина ${\displaystyle M_{p}}$ составляет ${\displaystyle p}$ бит, а алгоритм умножения двух чисел, например, «в столбик», имеет сложность ${\displaystyle O(p^{2})}$ . Так как возведение в квадрат в тесте происходит ${\displaystyle O(p)}$ раз, то вычислительная сложность алгоритма равна ${\displaystyle O(p^{3})}$ . Тест можно ускорить, если использовать алгоритмы быстрого умножения больших целых чисел, например, метод умножения Шёнхаге — Штрассена . Сложность теста в таком случае составит ${\displaystyle O(p^{2}\ln {p}\ln {\ln {p}})}$ .

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

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

${\displaystyle S_{p-1}=2^{p+1}-2=2(2^{p}-1)\equiv 0{\pmod {M_{p}}}}$ .

В 1930 году Лемер вывел критерий простоты для чисел вида ${\displaystyle k2^{n}-1}$ , где ${\displaystyle k<2^{n}}$ , а в 1969 году модифицировал тест Люка — Лемера для чисел такого вида, который впоследствии был дополнен Стечкиным . Возможно обобщение теста и на числа вида ${\displaystyle A2^{2n}+B2^{n}-1}$ .

были доказаны критерии простоты, аналогичные тесту Люка — Лемера, для чисел вида ${\displaystyle k3^{n}-1\;(k<3^{n})}$ и ${\displaystyle k2^{n}3^{m}-1,\;(k<2^{n}3^{m})}$ , а также для некоторых чисел вида ${\displaystyle kq^{n}-1}$ , где ${\displaystyle q>3}$ — простое ${\displaystyle (k<q^{n})}$ .

Существует более общий , который применим для любого натурального числа ${\displaystyle N}$ , если известно полное или частичное разложение на простые множители числа ${\displaystyle N-1}$ или ${\displaystyle N+1}$ .

Применения

Благодаря тесту Люка — Лемера, простые числа Мерсенна удерживают лидерство как самые большие известные простые числа , хотя и до существования теста числа Мерсенна почти всегда были наибольшими простыми. Так, в 1588 году была доказана простота чисел ${\displaystyle M_{17}}$ и ${\displaystyle M_{19}}$ .

Евклид доказал, что всякое число вида ${\displaystyle 2^{p-1}(2^{p}-1)=2^{p-1}M_{p}}$ — совершенное , если ${\displaystyle M_{p}}$ — простое, а Эйлер показал, что все чётные совершенные числа имеют такой вид ; поэтому тест Люка — Лемера фактически позволяет найти все чётные совершенные числа.

Именно этот тест лежит в основе проекта распределённых вычислений GIMPS , занимающегося поиском новых простых чисел Мерсенна , хотя до сих пор не доказано, что их бесконечно много .

Также данный тест используется для тестирования аппаратного обеспечения . Так, в 1992 году специалисты компании протестировали новый суперкомпьютер компании Cray , используя программу, написанную для поиска простых чисел Мерсенна. В результате за 19 часов работы программы было открыто простое число ${\displaystyle M_{756839}}$ .

Примечания