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

Материал из Википедии — свободной энциклопедии

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

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

Для простого числа p число Mp является простым тогда и только тогда, когда оно делит число Lp - 1, где числа Lk определяются рекуррентным соотношением: .

Для установления простоты M_p последовательность чисел достаточно вычислять по модулю числа 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 из Энциклопедии целочисленных последовательностей)

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

[править] Ссылки

• Последовательность Люка
• Lucas-Lehmer Test from MathWorld