Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

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

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

Для простого числа p число M_p является простым тогда и только тогда, когда оно делит число L_{p-1}, где числа L_k определяются рекуррентным соотношением: 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} \bmod M_p называется вычетом Люка — Лемера. Таким образом, число Мерсенна M_p является простым тогда и только тогда, когда число p простое, и вычет Люка — Лемера равен нулю.

Возможными значениями L_1 являются: 4, 10, 52, 724, 970, ... (Шаблон:Sloane)

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

Ссылки Править

Викия-сеть

Случайная вики