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

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

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

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

Для простого числа $p\geqslant 3$ число Mp является простым тогда и только тогда, когда оно делит число Lp - 1, где числа Lk определяются рекуррентным соотношением: $L_1 = 4, L_{k+1} = L_k^2 - 2$.

Для установления простоты 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 (третья серия).