Русская Википедия:Тест Люка — Лемера

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

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

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

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

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

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

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

<math>V_n(P,Q)=\alpha^n+\beta^n,</math>

<math>U_n(P,Q)=\frac{\alpha^n-\beta^n}{\alpha-\beta},</math>

где <math>\alpha,\;\beta</math> — корни квадратного уравнения

<math>x^2-Px+Q=0</math>

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

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

1. <math>V_n^2-DU_n^2=4Q^n</math>

2. <math>V_{2n}=V_n^2-2Q^n,\quad U_{2n}=U_nV_n</math>

3. <math>\frac{V_n+\sqrt{D}U_n}{2}=\left(\frac{P+\sqrt{D}}{2}\right)^n</math>

4. Если <math>P'\equiv P \pmod N</math>, <math>Q'\equiv Q \pmod N</math>, <math>(Q,N)=1</math> и

<math>QP'=P^2-2Q \pmod N</math>,

то

<math>\begin{cases}Q^nV_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}</math>

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

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

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

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

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

<math>2^nV_n(-4, 1)\equiv V_{2n}(2, -2)\pmod N</math>,

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

<math>V_{2n}(-4, 1)=V_n^2(-4, 1)-2</math>,

поэтому

<math>S_{p-1}\equiv V_{\frac{N+1}{4}}(-4,1)\pmod N</math>

и

<math>V_{\frac{N+1}{2}}(2,-2)\equiv 2^\frac{N+1}{4}S_{p-1}\pmod N</math>

<math>D=2^2-4\cdot(-2)=12</math>, поэтому если <math>N</math> — простое, то <math>\left(\frac{D}{N}\right)=-1</math> и из последних двух свойств <math>N</math> делит

<math>U_{N+1}(2,-2)=V_{\frac{N+1}{2}}(2,-2)U_{\frac{N+1}{2}}(2,-2)</math>

Далее, из свойств 1. и 2.

<math>V_{N+1}=V_{\frac{N+1}{2}}^2-2\cdot(-2)^\frac{N+1}{2}\equiv 8+4=12\pmod N</math>,

но по свойству 3.

<math>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</math>,

то есть <math>N</math> делит <math>V_{\frac{N+1}{2}}(2,-2)</math>, а значит и <math>S_{p-1}</math>.

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

Если <math>N</math> делит <math>S_{p-1}</math>, то из доказательства необходимости следует, что оно делит и <math>V_{\frac{N+1}{2}}</math>. <math>N</math> взаимно просто с <math>U_{\frac{N+1}{2}}</math> по свойству 1., а по свойству 2. — делит <math>U_{N+1}</math>. Но тогда каждый простой делитель числа <math>N</math> представим в виде <math>\pm 1 + k2^p>\sqrt{N}</math>, то есть <math>N=M_p</math> — простое.

История

Критерий простоты был предложен французским математиком Люка в 1878 году. В частности, Люка показал, что алгоритм позволяет проверять простоту <math>M_p</math> для простых <math>p\equiv 1 \pmod 4</math>. В 1930 году американский математик Лемер полностью доказал справедливость критерия для всех простых нечётных <math>p</math> в своей диссертации на соискание учёной степени доктора философии.

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

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

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

Примеры

Требование нечётности <math>p</math> в условии критерия существенно, так как <math>M_2=2^2-1=3</math> — простое, но <math>S_1\equiv 4 \pmod 3 = 1\not=0</math>.

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

<math>S_1=4</math>

<math>S_2\equiv 4^2-2\pmod {8191} = 14</math>

<math>S_3\equiv 14^2-2\pmod {8191}=194</math>

<math>S_4\equiv194^2-2\pmod {8191}=4870</math>

<math>S_5\equiv4870^2-2\pmod {8191}=3953</math>

<math>S_6\equiv3953^2-2\pmod {8191}=5970</math>

<math>S_7\equiv5970^2-2\pmod {8191}=1857</math>

<math>S_8\equiv1857^2-2\pmod {8191}=36</math>

<math>S_9\equiv36^2-2\pmod {8191}=1294</math>

<math>S_{10}\equiv1294^2-2\pmod {8191}=3470</math>

<math>S_{11}\equiv3470^2-2\pmod {8191}=128</math>

<math>S_{12}\equiv128^2-2\pmod {8191}=0</math>

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

<math>S_1=4</math>

<math>S_2\equiv 4^2-2\pmod {2047} = 14</math>

<math>S_3\equiv 14^2-2\pmod {2047}=194</math>

<math>S_4\equiv194^2-2\pmod {2047}=788</math>

<math>S_5\equiv788^2-2\pmod {2047}=701</math>

<math>S_6\equiv701^2-2\pmod {2047}=119</math>

<math>S_7\equiv119^2-2\pmod {2047}=1877</math>

<math>S_8\equiv1877^2-2\pmod {2047}=240</math>

<math>S_9\equiv240^2-2\pmod {2047}=282</math>

<math>S_{10}\equiv282^2-2\pmod {2047}=1736\not=0</math>

Действительно, <math>2047=23\cdot 89</math>.

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

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

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

<math>\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}</math>

При использовании этого способа деления по модулю вычислительная сложность теста будет определяться сложностью алгоритма возведения в квадрат. Длина <math>M_p</math> составляет <math>p</math> бит, а алгоритм умножения двух чисел, например, «в столбик», имеет сложность <math>O(p^2)</math>. Так как возведение в квадрат в тесте происходит <math>O(p)</math> раз, то вычислительная сложность алгоритма равна <math>O(p^3)</math>. Тест можно ускорить, если использовать алгоритмы быстрого умножения больших целых чисел, например, метод умножения Шёнхаге — Штрассена. Сложность теста в таком случае составит <math>O(p^{2}\ln{p}\ln{\ln{p}})</math>.

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

Условие в тесте можно ослабить и потребовать лишь, чтобы <math>S_{p-2}\equiv \pm 2^{\frac{p+1}{2}} \pmod {M_p}</math>, откуда немедленно следует:

<math>S_{p-1}=2^{p+1}-2=2(2^p-1) \equiv 0 \pmod {M_p}</math>.

В 1930 году Лемер вывел критерий простоты для чисел вида <math>k2^n-1</math>, где <math>k<2^n</math>, а в 1969 году Шаблон:Не переведено 5 модифицировал тест Люка — Лемера для чисел такого вида, который впоследствии был дополнен Стечкиным. Возможно обобщение теста и на числа вида <math>A2^{2n}+B2^{n}-1</math>.

Шаблон:Не переведено 5 были доказаны критерии простоты, аналогичные тесту Люка — Лемера, для чисел вида <math>k3^n-1\;(k<3^n)</math> и <math>k2^n3^m-1,\;(k<2^n3^m)</math>, а также для некоторых чисел вида <math>kq^n-1</math>, где <math>q>3</math> — простое <math>(k<q^n)</math>.

Существует более общий <math>(N^2-1)</math>-тест простоты, который применим для любого натурального числа <math>N</math>, если известно полное или частичное разложение на простые множители числа <math>N-1</math> или <math>N+1</math>.

Применения

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

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

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

Также данный тест используется для тестирования аппаратного обеспечения. Так, в 1992 году специалисты компании Шаблон:Нп5 протестировали новый суперкомпьютер компании Cray, используя программу, написанную Шаблон:Нп5 для поиска простых чисел Мерсенна. В результате за 19 часов работы программы было открыто простое число <math>M_{756839}</math>.

Примечания

Внешние ссылки