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

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

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

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

Уильямсом^[нем.] были доказаны критерии простоты, аналогичные тесту Люка — Лемера, для чисел вида ${\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^[англ.] протестировали новый суперкомпьютер компании Cray, используя программу, написанную Словински^[англ.] для поиска простых чисел Мерсенна. В результате за 19 часов работы программы было открыто простое число ${\displaystyle M_{756839}}$^[20].

Примечания

1. Jaroma J. H. Note on the Lucas–Lehmer Test (англ.) // Irish Mathematical Society Bulletin — IMS, 2004. — Vol. 54. — P. 63—72. — ISSN 0791-5578
2. последовательность A003010 в OEIS
3. Abhijit Das. Computational Number Theory. — 2-е изд. — CRC Press, 2016. — P. 290—292. — 614 p. — (Discrete Mathematics and Its Applications). — ISBN 1482205823.
4. Крэндалл Р., Померанс К. Простые числа. Криптографические и вычислительные аспекты = Prime Numbers: A Computational Perspective / пер. с англ. А. В. Бегунца, Я. В. Вегнера, В. В. Кнотько, С. Н. Преображенского, И. С. Сергеева. — М.: УРСС, Книжный дом «Либроком», 2011. — С. 198—216, 498—500, 510—513. — 664 с. — ISBN 978-5-453-00016-6, 978-5-397-02060-2.
5. Robinson R. M. Mersenne and Fermat Numbers (англ.) // Proceedings of the American Mathematical Society / K. Ono — AMS, 1954. — Vol. 5, Iss. 5. — P. 842. — ISSN 0002-9939; 1088-6826 — doi:10.2307/2031878
6. Kravitz S. The Lucas–Lehmer Test for Mersenne Numbers (англ.) // Fibonacci Quarterly / C. Cooper — The Fibonacci Association, 1970. — Vol. 8, Iss. 1. — P. 1—3. — ISSN 0015-0517; 2641-340X
7. последовательность A018844 в OEIS
8. Трост Э. Простые числа = Primzahlen / под ред. А. О. Гельфонда, пер. с нем. Н. И. Фельдмана. — М.: Физматлит, 1959. — С. 42—46. — 137 с. — 15 000 экз.
9. Уильямс Х. Проверка чисел на простоту с помощью вычислительных машин = Primality testing on a computer // Лупанов О. Б. Кибернетический сборник : журнал / пер. с англ. С. В. Чудова. — М.: Мир, 1986. — Вып. 23. — С. 51—99. — ISBN N/A, ББК 32.81, УДК 519.95.
10. Ribenboim P. The Little Book of Bigger Primes (англ.) — 2nd edition — Springer-Verlag New York, 2004. — P. 75—87. — 356 p. — ISBN 978-0-387-21820-5
11. Devlin K. Mathematics (англ.): The New Golden Age — 2nd edition — United Kingdom: Penguin Books, 1998. — P. 75—87. — 320 p. — ISBN 978-0-14-193605-5
12. GIMPS Discovers Largest Known Prime Number: 2^136,279,841-1 (англ.). GIMPS (23 октября 2024). Дата обращения: 23 октября 2024.
13. Koshy T. Elementary Number Theory with Applications. — 2nd edition. — Academic Press, 2007. — P. 369—381. — 800 p. — ISBN 9780080547091.
14. Bach E., Shallit J. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. — The MIT Press, 1996. — P. 41—66. — 496 p. — (Foundations of Computing). — ISBN 978-0262024051.
15. Williams H. C. A Class of Primality Tests for Trinomials Which Includes the Lucas-Lehmer Test (англ.) // Pacific Journal of Mathematics — Mathematical Sciences Publishers, 1982. — Vol. 98, Iss. 2. — P. 477—494. — ISSN 0030-8730; 1945-5844 — doi:10.2140/PJM.1982.98.477
16. Rosen K. H. Elementary Number Theory and Its Applications (англ.) — 5 — Addison-Wesley, 2004. — P. 261—265. — 744 p. — ISBN 978-0-321-23707-1
17. Хассе Г. Лекции по теории чисел = Vorlesungen über die Theorie der algebraischen Zahlen / под ред. И. Р. Шафаревича, пер. с нем. В. Б. Демьянова. — М.: Издательство иностранной литературы, 1953. — С. 36—44. — 528 с.
18. Mathematics and Research Strategy (англ.). GIMPS. Дата обращения: 4 декабря 2016. Архивировано 20 ноября 2016 года.
19. Wolf M. Computer Experiments with Mersenne Primes (англ.) // Computational Methods in Science and Technology — IBCH PAS, 2013. — Vol. 19, Iss. 3. — P. 157—165. — ISSN 1505-0602; 2353-9453 — doi:10.12921/CMST.2013.19.03.157-165 — arXiv:1112.2412
20. Clawson C. C. Mathematical Mysteries (англ.): The Beauty and Magic of Numbers — Springer US, 1996. — P. 174. — 314 p. — ISBN 978-0-306-45404-2 — doi:10.1007/978-1-4899-6080-1