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

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

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

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

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

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

Пусть $p$ — простое нечётное. Число Мерсенна $M_p=2^p-1$ простое тогда и только тогда, когда оно делит нацело $(p-1)$-й член последовательности $4,14,194,37634,\dots$ , задаваемой рекуррентно: $S_k=\{\begin{array}{ll}4& k=1,\\ S_{k-1}^2-2& k>1.\end{array}$ Лемер, 1930 год

Для проверки простоты $M_p$ последовательность чисел $S_1,S_2,\dots ,S_{p-1}$ вычисляется по модулю числа $M_p$ (то есть вычисляются не сами числа $S_k$, длина которых растёт экспоненциально, а остатки от деления $S_k$ на $M_p$, длина которых ограничена $p$ битами). Последнее число в этой последовательности $S_{p-1}{modM}_p$ называется вычетом Люка — Лемера. Таким образом, число Мерсенна $M_p$ является простым тогда и только тогда, когда число $p$ — нечётное простое и вычет Люка — Лемера равен нулю. Сам алгоритм можно записать в виде псевдокода:

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

Значения $S_1$, для которых справедлив критерий простоты, образуют последовательность: $4,10,52,724,970,10084,\dots$ .

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

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

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

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

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

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

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

$x^2-Px+Q=0$

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

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

1. $V_n^2-D{U}_n^2=4Q^n$

2. $V_{2n}=V_n^2-2Q^n,U_{2n}=U_n{V}_n$

3. $\frac{V_n+\sqrt{D}{U}_n}{2}={\left(\frac{P+\sqrt{D}}{2}\right)}^n$

4. Если $P^{\prime }\equiv P(\mathrm{mod}N)$, $Q^{\prime }\equiv Q(\mathrm{mod}N)$, $(Q,N)=1$ и

$Q{P}^{\prime }=P^2-2Q(\mathrm{mod}N)$,

то

$\{\begin{array}{l}{Q}^n{V}_n(P^{\prime },1)\equiv V_{2n}(P,Q)(\mathrm{mod}N)\\ P{Q}^{n-1}{U}_n(P^{\prime },1)\equiv U_{2n}(P,Q)(\mathrm{mod}N)\end{array}$

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

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

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

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

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

$2^n{V}_n(-4,1)\equiv V_{2n}(2,-2)(\mathrm{mod}N)$,

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

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

поэтому

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

и

$V_{\frac{N+1}{2}}(2,-2)\equiv 2^{\frac{N+1}{4}}{S}_{p-1}(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}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+k{2}^p>\sqrt{N}$, то есть $N=M_p$ — простое.

История

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

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

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

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

Примеры

Требование нечётности $p$ в условии критерия существенно, так как $M_2=2^2-1=3$ — простое, но $S_1\equiv 4(\mathrm{mod}3)=1=0$.

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

$S_1=4$

$S_2\equiv 4^2-2(\mathrm{mod}8191)=14$

$S_3\equiv 14^2-2(\mathrm{mod}8191)=194$

$S_4\equiv 194^2-2(\mathrm{mod}8191)=4870$

$S_5\equiv 4870^2-2(\mathrm{mod}8191)=3953$

$S_6\equiv 3953^2-2(\mathrm{mod}8191)=5970$

$S_7\equiv 5970^2-2(\mathrm{mod}8191)=1857$

$S_8\equiv 1857^2-2(\mathrm{mod}8191)=36$

$S_9\equiv 36^2-2(\mathrm{mod}8191)=1294$

$S_{10}\equiv 1294^2-2(\mathrm{mod}8191)=3470$

$S_{11}\equiv 3470^2-2(\mathrm{mod}8191)=128$

$S_{12}\equiv 128^2-2(\mathrm{mod}8191)=0$

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

$S_1=4$

$S_2\equiv 4^2-2(\mathrm{mod}2047)=14$

$S_3\equiv 14^2-2(\mathrm{mod}2047)=194$

$S_4\equiv 194^2-2(\mathrm{mod}2047)=788$

$S_5\equiv 788^2-2(\mathrm{mod}2047)=701$

$S_6\equiv 701^2-2(\mathrm{mod}2047)=119$

$S_7\equiv 119^2-2(\mathrm{mod}2047)=1877$

$S_8\equiv 1877^2-2(\mathrm{mod}2047)=240$

$S_9\equiv 240^2-2(\mathrm{mod}2047)=282$

$S_{10}\equiv 282^2-2(\mathrm{mod}2047)=1736=0$

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

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

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

Для целого числа $x$ и числа Мерсенна $M_p=2^p-1$ имеет место сравнение по модулю $x\equiv \left(x{mod2}^p\right)+\lfloor \frac{x}{2^p}\rfloor (\mathrm{mod}{M}_p)$, причём умножение на $2^k$ по модулю $M_p$ равносильно левому циклическому сдвигу на $k$ бит (если $k<0$, то сдвиг осуществляется в обратную сторону).

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

$\begin{array}{rl}916{mod2}^5-1& \equiv \left(916{mod2}^5\right)+\lfloor \frac{916}{2^5}\rfloor (\mathrm{mod}{2}^5-1)\\ & \equiv {10100}_2+{11100}_2(\mathrm{mod}{2}^5-1)\\ & \equiv {110000}_2(\mathrm{mod}{2}^5-1)\\ & \equiv {10000}_2+1_2(\mathrm{mod}{2}^5-1)\\ & \equiv {10001}_2(\mathrm{mod}{2}^5-1)\\ & ={10001}_2\\ & =17\end{array}$

При использовании этого способа деления по модулю вычислительная сложность теста будет определяться сложностью алгоритма возведения в квадрат. Длина $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}}(\mathrm{mod}{M}_p)$, откуда немедленно следует:

$S_{p-1}=2^{p+1}-2=2(2^p-1)\equiv 0(\mathrm{mod}{M}_p)$.

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

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

Существует более общий $(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 году специалисты компании AEA Technology протестировали новый суперкомпьютер компании Cray, используя программу, написанную Словински для поиска простых чисел Мерсенна. В результате за 19 часов работы программы было открыто простое число $M_{756839}$.