17-10-2023
Тест Люка́ — Ле́мера — эффективный тест простоты для чисел Мерсенна. Этот тест был предложен Люка в 1878 году и в 1930 году усовершенствован Лемером.
Тест Люка — Лемера базируется на том наблюдении, что простота числа Мерсенна влечёт простоту числа , и следующем утверждении:
|
Для простого числа p⩾3 число является простым тогда и только тогда, когда оно делит число , где числа определяются рекуррентным соотношением: , Lk+1 = Lk2 — 2 для всех k⩾1. |
Содержание |
Для установления простоты последовательность чисел вычисляется по модулю числа (т. е. вычисляются не сами числа , длина которых растёт экспоненциально; а остатки от деления на , длина которых ограничена p битами). Последнее число в этой последовательности называется вычетом Люка — Лемера. Таким образом, число Мерсенна является простым тогда и только тогда, когда число простое, и вычет Люка — Лемера равен нулю.
Возможными значениями являются: 4, 10, 52, 724, 970, 10084, … (последовательность A018844 в OEIS)
Lucas–Lehmer(p)
var s = 4
var M = 2p — 1
repeat p — 2 times:
s = ((s × s) — 2) mod M
if s = 0 return PRIME else return COMPOSITE
Благодаря тесту Люка — Лемера простые числа Мерсенна удерживают лидерство как самые большие известные простые числа. Именно тест Люка — Лемера лежит в основе проекта распределённых вычислений GIMPS, занимающимся поиском новых простых чисел Мерсенна.
| Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её. |
Тест Люка-Лемера.