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

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

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

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

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

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

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

${\displaystyle 4,\;14,\;194,\;37634,\;\ldots }$ ^[2],

задаваемой рекуррентно: ${\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}}$ называется вычетом Люка — Лемера^[3]. Таким образом, число Мерсенна ${\displaystyle M_{p}}$ является простым тогда и только тогда, когда число ${\displaystyle p}$ — нечётное простое и вычет Люка — Лемера равен нулю. Сам алгоритм можно записать в виде псевдокода^[4]:

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 }$ ^[5][6][7].

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

Если числа ${\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}$ взаимно просты.

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

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)}$ — символ Лежандра.

Схема доказательства^[9]:

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

Из свойства 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}}}$^[9]. В 1930 году американский математик Лемер полностью доказал справедливость критерия для всех простых нечётных ${\displaystyle p}$ в своей диссертации на соискание учёной степени доктора философии^[1].

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

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

Наибольшее из известных простых чисел Мерсенна на 2024 год, найденное с помощью теста Люка — Лемера, это ${\displaystyle M_{82589933}}$^[12]. Однако это не самое большое известное простое число Мерсенна. 11 октября 2024 года с помощью теста Ферма было найдено ${\displaystyle M_{136279841}}$. Поскольку тест Ферма является вероятностным, 12 октября был использован тест Люка — Лемера для проверки простоты; этот день является официальной датой открытия нового простого числа^[13].

Примеры

Требование нечётности ${\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}$ — простое^[14]. Действительно,

${\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}$ показывает, что оно составное^[14]:

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

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

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

Для целого числа ${\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})}$^[4]. Так как возведение в квадрат в тесте происходит ${\displaystyle O(p)}$ раз, то вычислительная сложность алгоритма равна ${\displaystyle O(p^{3})}$^[15]. Тест можно ускорить, если использовать алгоритмы быстрого умножения больших целых чисел, например, метод умножения Шёнхаге — Штрассена. Сложность теста в таком случае составит ${\displaystyle O(p^{2}\ln {p}\ln {\ln {p}})}$.

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

Условие в тесте можно ослабить^[8] и потребовать лишь, чтобы ${\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 году Ханс Ризель^[англ.] модифицировал тест Люка — Лемера для чисел такого вида, который впоследствии был дополнен Стечкиным^[9]. Возможно обобщение теста и на числа вида ${\displaystyle A2^{2n}+B2^{n}-1}$^[16].

Уильямсом^[нем.] были доказаны критерии простоты, аналогичные тесту Люка — Лемера, для чисел вида ${\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})}$^[9].

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

Применения

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

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

До 2018 года^[19] этот тест использовался в качестве основого в проекте распределённых вычислений GIMPS, занимающегося поиском новых простых чисел Мерсенна^[20], хотя до сих пор не доказано, что их бесконечно много^[21].

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