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

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

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

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

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

$4,\;14,\;194,\;37634,\;\ldots$ (последовательность A003010 в OEIS),

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

Лемер, 1930 год

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

Для доказательства теоремы в обе стороны воспользуемся функциями Люка:

$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}-DU_{n}^{2}=4Q^{n}$

2. $V_{2n}=V_{n}^{2}-2Q^{n},\quad 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'\equiv P{\pmod {N}}$, $Q'\equiv Q{\pmod {N}}$, $(Q,N)=1$ и

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

то

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

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

6. Если $U_{n}$ делится на $p^{\alpha }$, и $\alpha \geq 1$, тогда $U_{p^{\beta }n}$ делится на $p^{\alpha +\beta }$ при целых $\beta \geq 1$.

Положим $\varepsilon (p)=\left({\frac {3}{p}}\right)$.

7. $V_{\frac {p+1}{2}}=\left({\frac {2}{p}}\right)(1+3\varepsilon (p)){\pmod {p}}$, если $p\neq 2$, $P=4$, $Q=1$.

8. Если $N$ — целое число, и $m(N)$ — наименьшее натуральное число такое, что $U_{m(N)}=0{\pmod {N}}$, тогда $U_{n}$ кратно $N$ тогда и только тогда, когда $n$ кратно $m(N)$.

Приступим непосредственно к доказательству.

Первый способ

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

Положим $N=M_{p}$. Рассматривая свойство 4. по модулю $N$ при $P=2$, $Q=-2$, имеем:

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

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

$V_{2p}(-4,1)=V_{p}^{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}$ — простое.

Второй способ

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

Рассмотрим последовательности Люка $U_{n}=U_{n}(4,1)$ и $V_{n}=V_{n}(4,1)$ и положим $N=M_{p}$.

Покажем сначала, что если $N$ — простое, то $S_{p-1}=V_{2^{p-1}}=0{\pmod {N}}$. Обратимся к свойству 7.

Так как $2\equiv (2^{(p+1)/2})^{2}{\pmod {N}}$, то 2 - квадратичный вычет по модулю числа N. Следовательно, $\left({\frac {2}{N}}\right)=1$.

Так как $p$ - нечётно, то $N=2^{p}-1\equiv 1=1^{2}{\pmod {3}}$, следовательно N - квадратичный вычет по модулю 3 и $\left({\frac {N}{3}}\right)=1$.

Применяя квадратичный закон взаимности, получаем:

$\left({\frac {3}{N}}\right)=\left({\frac {N}{3}}\right)\cdot (-1)^{{\frac {N-1}{2}}{\frac {3-1}{2}}}=-1$.

По свойству 7. получаем, что $V_{\frac {(N-1)+1}{2}}=V_{2^{N}}=1\cdot (1+3\cdot (-1))=-2{\pmod {N}}$, а так как $V_{2^{N}}=V_{2^{N-1}}^{2}-2$, то $V_{2^{N-1}}=0{\pmod {N}}$, что и требовалось доказать.

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

Осталось показать, что если $V_{2^{p-1}}=0$, то число $N=M_{p}=2^{p}-1$ - простое.

Покажем, что $m(N)$ (минимальный индекс $m$, при котором $U_{m}$ делится на $N$) равен $2^{p}$.

Так как при любых k $U_{2k}=U_{k}V_{k}$, то $U_{2^{p}}=U_{2^{p-1}}V_{2^{p-1}}=0{\pmod {N}}$. По свойству 8. тогда $m(N)$ должно быть делителем числа $2^{p}$.

Более того, из $2U_{k+1}=4U_{k}+V_{k}$ следует, что $\gcd {(U_{k},V_{k})}\leq 2$. Отсюда следует, что $U_{k}$ и $V_{k}$ не имеют общих нечетных делителей. Так что если $V_{2^{p-1}}$ делится на (нечётное число!) $N$, то $U_{2^{p-1}}$ с этим числом взаимно просто. Значит, опять по свойству 8., $m(N)$ не является делителем чиcла $2^{p-1}$. В сочетании со сказанным выше, это означает, что $m(N)=2^{p}$.

Пусть $N={p_{1}}^{e_{1}}...{p_{r}}^{e_{r}}$ - разложение числа M на простые множители. Числа $p_{j}$ больше 3, так как $k$ нечетное и выполняется $k=2^{p}-1=(-1)^{p}-1=-2{\pmod {3}}$, $N$ — простое по условию.

Используя 6., получим $U_{t}=0{\pmod {2^{p}-1}}$, где

$t=\mathrm {lcm} ({p_{1}}^{e_{1}-1}(p_{1}-\varepsilon (p_{1})),\dots ,{p_{r}}^{e_{r}-1}(p_{r}-\varepsilon (p_{r})))$.

По свойству 8. отсюда следует, что t кратно $m(N)$. Положим

$n_{0}=\prod _{j=1}^{r}{p_{j}}^{e_{j}-1}(p_{j}-\varepsilon (p_{j}))\leq \prod _{j=1}^{r}{p_{j}}^{e_{j}-1}(p_{j}+1/5p_{j})=(6/5)^{r}N$.

Так как $p_{j}-\varepsilon (p_{j})$ — число четное, то

$t=2\cdot \mathrm {lcm} ({p_{1}}^{e_{1}-1}{\frac {p_{1}-\varepsilon (p_{1})}{2}},\dots ,{p_{r}}^{e_{r}-1}{\frac {p_{r}-\varepsilon (p_{r})}{2}})\leq {n_{0}}/2^{r-1}$.

Используем ранее доказанные факты, получим

$m(N)\leq {t}\leq 2(3/5)^{r}N<2(3/5)^{r}\cdot 2m(N)<3m(N)$;

Следовательно $r\leq 2$ и $t=m(N)$ либо $t=2m(N)$. Заметим, что $t$ — степень двойки. Отсюда следует, что $e_{1}=1$ и $e_{r}=1$.

Если $N$ — составное, то должно быть $N=2^{p}-1=(2^{k}+1)(2^{l}-1)$, где $2^{k}+1$ и $2^{l}-1$ — простые числа. Но число p делится на l! Действительно, имеем: $2^{p}-1$ делится на $2^{l}-1$. Разделим $p$ на $l$ с остатком: $p=lq+r(0\leq r<l)$. Тогда $2^{p}-1=(2^{p}-2^{r})+(2^{r}-1)$. Первое слагаемое делится на $2^{l}-1$, а второе - меньше, чем $2^{l}-1$. Поэтому $2^{p}-1$ может делиться на $2^{l}-1$ только если $(2^{r}-1)=0$. Но тогда $r=0$ и $p$ делится на $l$, что противоречит условию, что $p$ - простое число.

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

Возможными значениями $S_{1}$ являются: $4,\;10,\;52,\;724,\;970,\;10084,\;\ldots$ (последовательность A018844 в OEIS).

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

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

История

Критерий простоты был предложен французским математиком Люка в 1878 году и усовершенствован американским математиком Лемером в 1932 году. В частности, Люка показал, что алгоритм позволяет проверять простоту $M_{p}$ для простых $p\equiv 1{\pmod {4}}$, но Лемер был первым, кто доказал справедливость критерия для всех нечетных простых $p$. В 1952 году Робинсон при поддержке Лемера провел вычисления на компьютере SWAC с использованием теста Люка — Лемера, результатом которого стало открытие простых чисел $M_{521}$ и $M_{607}$. Позднее в этом же году были открыты $M_{1279}$, $M_{2203}$ и $M_{2281}$.

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

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

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

Вычислительная сложность теста для числа $M_{p}=2^{p}-1$ равна $O(p^{3})$, так как в процессе выполнения теста производится $O(p)$ возведений в квадрат и вычитаний по модулю $M_{p}$. Длина $M_{p}$ составляет $p$ бит, причём самый простой алгоритм умножения чисел имеет сложность $O(p^{2})$. Для ускорения теста следует использовать алгоритмы быстрого умножения больших целых чисел, например, метод умножения Шёнхаге — Штрассена. Сложность теста в таком случае составит $O(p^{2}\log {p}\log {\log {p}})$.

Примеры

Требование нечетности $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}\equiv 194^{2}-2{\pmod {8191}}=4870$

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

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

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

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

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

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

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

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

Следовательно, число $M_{13}={8191}$ — простое.

Покажем, что число $M_{11}=2^{11}-1=2047=23\cdot 89$ — составное. Действительно:

$S_{1}=4$

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

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

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

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

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

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

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

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

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

Псевдокод

Lucas–Lehmer(p)
    var S = 4
    var M = 2p — 1
    repeat p — 2 times:
        S = ((S × S) — 2) mod M
    if S = 0 return PRIME else return COMPOSITE

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

Условие в тесте можно ослабить и потребовать лишь, чтобы $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^{n}3^{m},\;(k<2^{n}3^{m})$, а также для некоторых чисел вида $kq^{n}-1$, где $q>3$ — простое $(k<q^{n})$.

Отметим, что есть более общие $(N\pm 1)$-методы простоты, которые применимы для любого натурального числа $N$, если известно полное или частичное разложение на простые множители числа $N-1$ или $N+1$.

Применения

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

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

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

Также данный тест используется для тестирования аппаратного обеспечения

См. также

• Числа Мерсенна
• Тест простоты
• GIMPS