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

---

Те́ст Люка́ — Ле́мера (англ. Lucas-Lehmer test, сокр. LLT) — полиномиальный, детерминированный и безусловный (то есть не зависящий от недоказанных гипотез) тест простоты для чисел Мерсенна. Сформулирован Эдуардом Люка в 1878 году и доказан Лемером в 1930 году^[⇨].

При заданном простом числе ${\displaystyle p>2}$ тест позволяет за полиномиальное время^[⇨] от битовой длины ${\displaystyle p}$ числа Мерсенна ${\displaystyle M_{p}=2^{p}-1}$ определить, является ${\displaystyle M_{p}}$ простым или составным^[⇨]. Доказательство справедливости теста существенно опирается на функции Люка^[⇨], что позволило обобщить тест Люка — Лемера на некоторые числа, вид которых отличен от чисел Мерсенна^[⇨].

Благодаря этому тесту самыми большими известными простыми числами почти всегда были простые числа Мерсенна, причём даже до появления компьютеров; именно он лежит в основе проекта распределённых вычислений GIMPS, занимающегося поиском новых простых чисел Мерсенна. Также он интересен своей связью с чётными совершенными числами^[⇨].

Пусть ${\displaystyle p}$ — простое нечётное. Число Мерсенна ${\displaystyle M_{p}=2^{p}-1}$ простое тогда и только тогда, когда оно делит нацело ${\displaystyle (p-1)}$-й член последовательности

---