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

Те́ст Люка́ — Ле́мера (англ. 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,\;\ldots$ ,

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

Лемер, 1930 год

Для проверки простоты $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$ — нечётное простое и вычет Люка — Лемера равен нулю. Сам алгоритм можно записать в виде псевдокода:

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,\;\ldots$ .

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

Если числа $p=4n+3$ и $q=2p+1=8n+7$ — простые, то $M_{p}\equiv 0{\pmod {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}-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)$ — символ Лежандра.

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

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

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

$2^{n}V_{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 в Калифорнийском университете.

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

Примеры

Требование нечётности $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_{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}\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$

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

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

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

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

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

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

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