WikiSort.ru - Не сортированное

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

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

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

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

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

Для проверки простоты ${\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]:

Lucas–Lehmer(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 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]:

История

Критерий простоты был предложен французским математиком Люка в 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].

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

Примеры

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

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

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

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

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

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

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

Примечания

Эта статья входит в число хороших статей русскоязычного раздела Википедии.