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

Тест Люка́ — Ле́мера — эффективный тест простоты для чисел Мерсенна. Этот тест был предложен Люка в 1878 году и в 1930 году усовершенствован Лемером.

Тест Люка — Лемера базируется на том наблюдении, что простота числа Мерсенна M_p = 2^p - 1 влечёт простоту числа p, и следующем утверждении:

Для простого числа p⩾3 число Mp является простым тогда и только тогда, когда оно делит число Lp − 1, где числа Lk определяются рекуррентным соотношением: L1 = 4, Lk+1 = Lk2 — 2 для всех k⩾1.

Описание

Для установления простоты M_p последовательность чисел $L_1, L_2, \ldots, L_{p-1}$ вычисляется по модулю числа M_p (т. е. вычисляются не сами числа L_k, длина которых растёт экспоненциально; а остатки от деления L_k на M_p, длина которых ограничена p битами). Последнее число в этой последовательности L_{p − 1}mod M_p называется вычетом Люка — Лемера. Таким образом, число Мерсенна M_p является простым тогда и только тогда, когда число p простое, и вычет Люка — Лемера равен нулю.

Возможными значениями L₁ являются: 4, 10, 52, 724, 970, … (последовательность A018844 в OEIS)

Применения

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

Литература

• Weisstein, Eric W. Lucas-Lehmer Test (англ.) на сайте Wolfram MathWorld.
• А.Н.Рудаков Числа Фибоначчи и простота числа 2¹²⁷-1 // Математическое Просвещение. — 2000. — В. 4 (третья серия).