Просмотр кода страницы Тест Люка — Лемера

'''Те́ст Люка́ — Ле́мера''' ({{lang-en|Lucas-Lehmer test}}, сокр. '''''LLT''''') — [[Полиномиальный алгоритм|полиномиальный]], [[Детерминированный алгоритм|детерминированный]] и безусловный (то есть не зависящий от недоказанных гипотез) [[тест простоты]] для [[числа Мерсенна|чисел Мерсенна]]. Сформулирован [[Люка, Франсуа Эдуард Анатоль|Эдуардом Люка]] в [[1878 год в науке|1878 году]] и доказан [[Лемер, Деррик Генри|Лемером]] в [[1930 год в науке|1930 году]]{{переход|#История}}. 

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

Благодаря этому тесту [[Наибольшее известное простое число|самыми большими известными простыми числами]] почти всегда были простые числа Мерсенна, причём даже до появления [[Компьютер|компьютеров]]. До 2018 года он был основным тестом простоты в рамках проекта [[распределённые вычисления|распределённых вычислений]] [[GIMPS]], занимающегося поиском новых простых чисел Мерсенна. Также он интересен своей связью с [[Совершенное число#История изучения|чётными совершенными числами]]{{переход|#Применения}}.

== Формулировка ==
Тест основывается на следующем критерии простоты [[Число Мерсенна|чисел Мерсенна]]<ref name="bull" />:

{{теорема|1= Пусть <math>p</math> — [[Простое число|простое]] нечётное. Число Мерсенна <math>M_p=2^p-1</math> простое тогда и только тогда, когда оно делит нацело <math>(p-1)</math>-й член [[Числовая последовательность|последовательности]]

: <math>4,\; 14,\; 194,\; 37634,\; \ldots</math> <ref>{{Sloane|A003010}}</ref>,

задаваемой [[Рекуррентная формула|рекуррентно]]: <math>
  S_k=
   \begin{cases}
    4 & k=1,
   \\
    S_{k-1}^2-2 & k>1.
   \end{cases}
 </math>

|2=[[Лемер, Деррик Генри|Лемер]], [[1930 год в науке|1930 год]]}}

Для проверки простоты <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> называется '''вычетом Люка — Лемера'''<ref name="das">{{книга
 | автор         = Abhijit Das
 | часть         = 
 | ссылка часть  = 
 | заглавие      = Computational Number Theory
 | оригинал      = 
 | ссылка        = 
 | викитека      = 
 | ответственный = 
 | издание       = 2-е изд
 | место         = 
 | издательство  = CRC Press
 | год           = 2016
 | volume        = 
 | pages         = 290—292
 | columns       = 
 | allpages      = 614
 | серия         = Discrete Mathematics and Its Applications
 | isbn          = 1482205823
 | doi           = 
}}</ref>. Таким образом, число Мерсенна <math>M_p</math> является простым тогда и только тогда, когда число <math>p</math> — нечётное простое и вычет Люка — Лемера равен нулю. Сам алгоритм можно записать в виде псевдокода<ref name="pomer" />:

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

Значения <math>S_1</math>, для которых справедлив критерий простоты, образуют последовательность: <math>4,\;10,\;52,\;724,\;970,\;10084,\;\ldots</math> <ref name="rob">{{source|Q27965171|ref=Robinson|ref-year=1954}} <!-- Mersenne and Fermat Numbers // Proceedings of the American Mathematical Society --></ref><ref name="Kravitz">{{source|Q28107129|ref=Kravitz|ref-year=1970}} <!-- The Lucas–Lehmer Test for Mersenne Numbers // Fibonacci Quarterly --></ref><ref>{{Sloane|A018844}}</ref>. 

Не обязательно проверять все простые нечётные <math>p</math> при непосредственном переборе, поскольку некоторые числа Мерсенна специального вида всегда являются составными, что следует, например, из следующей доказанной [[Эйлер, Леонард|Эйлером]] теоремы<ref name="trost">{{книга
 | автор         = Трост Э.
 | часть         = 
 | ссылка часть  = 
 | заглавие      = Простые числа
 | оригинал      = Primzahlen
 | ссылка        = 
 | викитека      = 
 | ответственный = под ред. А. О. Гельфонда, пер. с нем. Н. И. Фельдмана
 | издание       = 
 | место         = М.
 | издательство  = Физматлит
 | год           = 1959
 | том           = 
 | страницы      = 42—46
 | столбцы       = 
 | страниц       = 137
 | серия         = 
 | isbn          = 
 | doi           = 
 | тираж         = 15000
 | ref           = 
}}</ref>:

{{теорема|1=Если числа <math>p=4n+3</math> и <math>q=2p+1=8n+7</math> — простые, то <math>M_p\equiv 0\pmod q</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> [[Взаимно простые числа|взаимно просты]].

В частности, при доказательстве используются некоторые свойства этих функций, а именно<ref name="lupa">{{статья
 |автор         = Уильямс Х.
 |заглавие      = Проверка чисел на простоту с помощью вычислительных машин
 |оригинал      = Primality testing on a computer
 |ссылка        = 
 |язык          = 
 |ответственный = пер. с англ. С. В. Чудова
 |автор издания = Лупанов О. Б.
 |издание       = Кибернетический сборник
 |тип           = журнал
 |место         = М.
 |издательство  = Мир
 |год           = 1986
 |месяц         = 
 |число         = 
 |том           = 
 |выпуск        = 23
 |номер         = 
 |страницы      = 51—99
 |isbn          = N/A, ББК 32.81, УДК 519.95
 |issn          = 
 |doi           = 
 |bibcode       =
 |arxiv         = 
 |pmid          = 
 |archiveurl    =
 |archivedate   =
}}</ref>:

: 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> — [[символ Лежандра]].

Схема доказательства<ref name="lupa" />:

===Необходимость===
Из свойства 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 год в науке|1878 году]]. В частности, Люка показал, что алгоритм позволяет проверять простоту <math>M_p</math> для простых <math>p\equiv 1 \pmod 4</math><ref name="lupa" />. В [[1930 год в науке|1930 году]] американский математик [[Лемер, Деррик Генри|Лемер]] полностью доказал справедливость критерия для всех простых нечётных <math>p</math> в своей [[Диссертация|диссертации]] на соискание [[Учёная степень|учёной степени]] [[Доктор философии|доктора философии]]<ref name="bull">{{source|Q27965254|ref=Jaroma|ref-year=2004}} <!-- Note on the Lucas-Lehmer Test // Irish Math. Soc. Bulletin --></ref>.

В 1952 году [[Робинсон, Рафаэль|Робинсон]] при поддержке Лемера провел вычисления на компьютере [[SWAC]] с использованием теста Люка — Лемера, результатом которого стало открытие простых чисел <math>M_{521}</math> и <math>M_{607}</math>. Позднее в этом же году были открыты <math>M_{1279}</math>, <math>M_{2203}</math> и <math>M_{2281}</math><ref name=Ribenboim>{{source|Q28122635|ref=Ribenboim|ref-year=2004|pages=75—87}} <!-- The Little Book of Bigger Primes --></ref>.

Лёгкость реализации теста и рост вычислительных мощностей компьютеров позволили фактически любому человеку заниматься поиском простых чисел Мерсенна. Так, в 1978 году два американских старшеклассника Лора Никель и Курт Нолл (Лемер преподавал им теорию чисел) за 3 года работы доказали простоту числа <math>M_{21701}</math>, используя [[суперкомпьютер]] [[Control Data Corporation|CDC]] [[CDC Cyber|Cyber 176]] в [[Калифорнийский университет|Калифорнийском университете]]<ref name="dev">{{source|Q27965329|ref=Devlin|ref-year=1998|pages=75-87}} <!-- Mathematics: The New Golden Age --></ref>.

Наибольшее из известных простых чисел Мерсенна на 2024 год, найденное с помощью теста Люка — Лемера, это <math>M_{82589933}</math><ref>{{cite web
 |url          = https://www.mersenne.org/primes/press/M82589933.html
 |title        = GIMPS Project Discovers Largest Known Prime Number: 2<sup>82,589,933</sup>-1
 |author       = 
 |date         = 2018-12-21
 |work         = [[GIMPS]]
 |publisher    = 
 |accessdate   = 2019-02-28
 |lang         = en
 |archive-date = 2020-08-15
 |archive-url  = https://archive.today/20200815183924/https://www.mersenne.org/primes/press/M82589933.html
 |deadlink     = no
}}</ref>. Однако это не самое большое известное простое число Мерсенна. 11 октября 2024 года с помощью [[Тест Ферма|теста Ферма]] было найдено <math>M_{136279841}</math>. Поскольку тест Ферма является вероятностным, 12 октября был использован тест Люка — Лемера для проверки простоты; этот день является официальной датой открытия нового простого числа<ref name=top>{{cite web
 |url          = https://www.mersenne.org/primes/?press=M136279841
 |title        = GIMPS Discovers Largest Known Prime Number: 2<sup>136,279,841</sup>-1
 |author       = 
 |date         = 2024-10-23
 |work         = [[GIMPS]]
 |publisher    = 
 |accessdate   = 2024-10-23
 |lang         = en
}}</ref>.

== Примеры ==
Требование [[Нечётное число|нечётности]] <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> — простое<ref name="koshy">{{книга
 | автор         = Koshy T.
 | часть         = 
 | ссылка часть  = 
 | заглавие      = Elementary Number Theory with Applications
 | оригинал      = 
 | ссылка        = 
 | викитека      = 
 | ответственный = 
 | издание       = 2nd edition
 | место         = 
 | издательство  = Academic Press
 | год           = 2007
 | volume        = 
 | pages         = 369—381
 | columns       = 
 | allpages      = 800
 | серия         = 
 | isbn          = 9780080547091
 | doi           = 
 | тираж         = 
}}</ref>. Действительно,
: <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> показывает, что оно составное<ref name="koshy" />:

: <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>.

== Вычислительная сложность ==
В рассматриваемом тесте две основные операции: возведение в квадрат и [[деление с остатком|деление по модулю]]. Эффективный [[алгоритм]] деления по модулю [[Число Мерсенна|числа Мерсенна]] на [[Компьютер|компьютере]] (фактически сводящийся к нескольким операциям [[Битовый сдвиг|битового сдвига]]) дает следующая теорема<ref name="pomer">{{книга
 | автор         = Крэндалл Р., Померанс К.
 | часть         = 
 | ссылка часть  = 
 | заглавие      = Простые числа. Криптографические и вычислительные аспекты
 | оригинал      = Prime Numbers: A Computational Perspective
 | ссылка        = 
 | викитека      = 
 | ответственный = пер. с англ. А. В. Бегунца, Я. В. Вегнера, В. В. Кнотько, С. Н. Преображенского, И. С. Сергеева
 | издание       = 
 | место         = М.
 | издательство  = УРСС, Книжный дом «Либроком»
 | год           = 2011
 | том           = 
 | страницы      = 198—216, 498—500, 510—513
 | столбцы       = 
 | страниц       = 664
 | серия         = 
 | isbn          = 978-5-453-00016-6, 978-5-397-02060-2
 | doi           = 
 | тираж         = 
 | ref           = 
}}</ref>:

{{теорема|1=Для [[целое число|целого]] числа <math>x</math> и  числа Мерсенна <math>M_p=2^p-1</math> имеет место [[сравнение по модулю]]

: <math>x\equiv \left(x\bmod 2^p\right)+\left\lfloor \frac{x}{2^p}\right\rfloor \pmod {M_p}</math>,
причём умножение на <math>2^k</math> по модулю <math>M_p</math> равносильно  [[Битовый сдвиг#Циклический сдвиг|левому циклическому сдвигу]] на <math>k</math> [[бит]] (если <math>k<0</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><ref name="pomer" />. Так как возведение в квадрат в тесте происходит <math>O(p)</math> раз, то вычислительная сложность алгоритма равна <math>O(p^3)</math><ref name=bach>{{книга
|заглавие = Algorithmic Number Theory, Vol. 1: Efficient Algorithms
|автор = Bach E., Shallit J.
|isbn = 978-0262024051
|pages = 41—66
|allpages = 496
|год =  1996
|издательство = The MIT Press
|серия = Foundations of Computing
}}</ref>. Тест можно ускорить, если использовать алгоритмы быстрого умножения больших целых чисел, например, [[метод умножения Шёнхаге — Штрассена]]. Сложность теста в таком случае составит <math>O(p^{2}\ln{p}\ln{\ln{p}})</math>.

== Вариации и обобщения ==
Условие в тесте можно ослабить<ref name="trost" /> и потребовать лишь, чтобы <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|Ризель, Ханс|Ханс Ризель|en|Hans Riesel}} [[Тест Люка — Лемера — Ризеля|модифицировал]] тест Люка — Лемера для чисел такого вида, который впоследствии был дополнен [[Стечкин, Сергей Борисович|Стечкиным]]<ref name="lupa" />. Возможно обобщение теста и на числа вида <math>A2^{2n}+B2^{n}-1</math><ref name="Williams">{{source|Q28016962|ref=Williams|ref-year=1982}} <!-- A Class of Primality Tests for Trinomials Which Includes the Lucas-Lehmer Test // Pacific Journal of Mathematics --></ref>.

{{не переведено 5|Уильямс, Хью|Уильямсом|de|Hugh C. Williams}} были доказаны критерии простоты, аналогичные тесту Люка — Лемера, для чисел вида <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><ref name="lupa" />.

Существует более общий [[Тест Бриллхарта — Лемера — Селфриджа|<math>(N^2-1)</math>-тест простоты]], который применим для любого [[Натуральное число|натурального числа]] <math>N</math>, если известно полное или частичное [[Факторизация целых чисел|разложение на простые множители]] числа <math>N-1</math> или <math>N+1</math><ref name="pomer" />.

== Применения ==
Во многом благодаря тесту Люка — Лемера, [[Число Мерсенна#Определения|простые числа Мерсенна]] удерживают лидерство как [[Наибольшее известное простое число|самые большие известные простые числа]], хотя и до существования теста числа Мерсенна почти всегда были наибольшими простыми. Так, в 1588 году была доказана простота чисел <math>M_{17}</math> и <math>M_{19}</math><ref name="Rosen">{{source|Q28122514|ref=Rosen|ref-year=2004|pages=261-265}} <!-- Elementary Number Theory and Its Applications --></ref>.

[[Евклид]] доказал, что всякое число вида <math>2^{p-1}(2^p-1)=2^{p-1}M_p</math> — [[Совершенное число|совершенное]], если <math>M_p</math> — простое, а [[Эйлер, Леонард|Эйлер]] показал, что все чётные совершенные числа имеют такой вид<ref name="has">{{книга
 | автор         = Хассе Г.
 | часть         = 
 | ссылка часть  = 
 | заглавие      = Лекции по теории чисел
 | оригинал      = Vorlesungen über die Theorie der algebraischen Zahlen
 | ссылка        = 
 | викитека      = 
 | ответственный = под ред. И. Р. Шафаревича, пер. с нем. В. Б. Демьянова
 | издание       = 
 | место         = М.
 | издательство  = Издательство иностранной литературы
 | год           = 1953
 | том           = 
 | страницы      = 36—44
 | столбцы       = 
 | страниц       = 528
 | серия         = 
 | isbn          = 
 | doi           = 
 | тираж         = 
 | ref           = 
}}</ref>; поэтому тест Люка — Лемера фактически позволяет найти все чётные совершенные числа.

До 2018 года<ref name="автоссылка1">{{Cite web|url=https://www.mersenne.org/various/math.php|title=GIMPS - The Math - PrimeNet|website=www.mersenne.org|access-date=2025-01-26}}</ref> этот тест использовался в качестве основого в проекте [[распределённые вычисления|распределённых вычислений]] [[GIMPS]], занимающегося поиском новых простых чисел Мерсенна<ref name="gimps">{{cite web
 |url          = http://www.mersenne.org/various/math.php
 |title        = Mathematics and Research Strategy
 |author       = 
 |date         = 
 |work         = [[GIMPS]]
 |publisher    = 
 |accessdate   = 2016-12-04
 |lang         = en
 |archive-date = 2016-11-20
 |archive-url  = https://web.archive.org/web/20161120091807/http://www.mersenne.org/various/math.php
 |deadlink     = no
}}</ref>, хотя до сих пор не доказано, что их бесконечно много<ref name="wolf">{{source|Q28016895|ref=Wolf|ref-year=2013}} <!-- Computer Experiments with Mersenne Primes // Computational Methods in Science and Technology --></ref>.

Также данный тест используется для тестирования [[Аппаратное обеспечение|аппаратного обеспечения]]. Так, в 1992 году специалисты компании {{нп5|AEA Technology|AEA Technology||AEA Technology}} протестировали новый [[суперкомпьютер]] компании [[Cray]], используя программу, написанную {{нп5|Словински, Дэвид|Словински||David Slowinski}} для поиска простых чисел Мерсенна. В результате за 19 часов работы программы было открыто простое число <math>M_{756839}</math><ref name="myst">{{source|Q28016914|ref=Clawson|ref-year=1996|pages=174}} <!-- Mathematical Mysteries: The Beauty and Magic of Numbers --></ref>.

== Примечания ==
{{примечания|2}}

{{^}}
{{Внешние ссылки}}
{{Теоретико-числовые алгоритмы}}

{{Хорошая статья|Математика}}

[[Категория:Тесты простоты]]