Тест Люка — Лемера — ефективний тест простоти для чисел Мерсенна. Завдяки цьому тесту найбільшими відомими простими числами завжди були прості числа Мерсенна, причому навіть до появи комп'ютерів[1].
Тест був запропонований французьким математиком Люка 1878 року і доповнений американським математиком Лемером[en] 1930 року. Отриманий тест носить ім'я двох вчених, які спільно відкрили його, навіть не зустрічаючись за життя. 1952 року Робінсон за підтримки Лемера провів обчислення на комп'ютері SWAC з використанням тесту Люка — Лемера, результатом якого стало відкриття простих чисел
і
. Пізніше того ж року були відкриті
,
і
[1].
Тест Люка — Лемера базується на тому спостереженні, що простота числа Мерсенна
тягне простоту числа
, і в наступному твердженні:
Для встановлення простоти
послідовність чисел
обчислюється по модулю числа
(тобто обчислюються не власне числа
, довжина яких росте експоненціально, а остачі від ділення
на
, довжина яких обмежена p бітами). Останнє число в цій послідовності
називається вирахуванням Люка — Лемера. Таким чином, число Мерсенна
є простим тоді і тільки тоді, коли число
просте, і вирахування Люка — Лемера дорівнює нулю.
Можливими значеннями
є: 4, 10, 52, 724, 970, 10084, …
Обчислювальна складність тесту для числа
дорівнює
[2], оскільки в процесі тесту виконується
піднесення до квадрату та вирахувань по модулю
. Довжина
становить
біт, причому найпростіший алгоритм множення чисел має складність
. Для прискорення тесту слід використовувати алгоритми швидкого множення великих цілих чисел, наприклад, алгоритм Шьонхаге — Штрассена. Складність тесту в такому випадку становитиме
.
Розглянемо виконання тесту для числа Мерсенна
.
![{\displaystyle L_{0}=4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/312ff70f117503578e567fcc540673e78c352f58)
![{\displaystyle L_{1}=4^{2}-2\mod {8191}=14}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b29088a5a58d93347106acccb3be91c99e8c4d31)
![{\displaystyle L_{2}=14^{2}-2\mod {8191}=194}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b3e0f1b6c293df3b788b4d05a87ba9d86d8e5ff)
![{\displaystyle L_{3}=194^{2}-2\mod {8191}=4870}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dec366c8d3c582bbd7beab34cce367a0a1e0f81c)
![{\displaystyle L_{4}=4870^{2}-2\mod {8191}=3953}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b884df69d46fab1d4aababa93b0b08d937f6aa5f)
![{\displaystyle L_{5}=3953^{2}-2\mod {8191}=5970}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05e8b6cec2606c8550d07a645d527c1ee86bfe1f)
![{\displaystyle L_{6}=5970^{2}-2\mod {8191}=1857}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca165f470bb169d2db0705a93405592b378ae8b9)
![{\displaystyle L_{7}=1857^{2}-2\mod {8191}=36}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbb6d384aa434bd81c1c9339c94cbd24325a3528)
![{\displaystyle L_{8}=36^{2}-2\mod {8191}=1294}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4eb66ea9887e43286bab3c07a2668b94d254eb19)
![{\displaystyle L_{9}=1294^{2}-2\mod {8191}=3470}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7f7ef707a2d9a712dc9d69c2e5d10c2649ac98d)
![{\displaystyle L_{10}=3470^{2}-2\mod {8191}=128}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1c197404d5a40070cef6c4a6dca8fb5fd4f8ce7c)
![{\displaystyle L_{11}=128^{2}-2\mod {8191}=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd0f4f4e812432346116165b03e19644a88707d8)
Отже, число
— просте.
Теорема: Нехай
— просте число, причому
. Визначимо послідовність
таким чином:
![{\displaystyle L_{0}=4,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10d4107f7db9f089d0e4d04ac637fead7280e187)
![{\displaystyle L_{n+1}=({L_{n}}^{2}-2)\mod (2^{q}-1).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8553fb075a7b4176e53fb4c658f14c50844d7dc1)
Тоді
— просте тоді і тільки тоді, коли
.
Доведення теореми засновано на властивостях послідовностей Люка
і
:
![{\displaystyle U_{0}=0,U_{1}=1,U_{n+1}=4U_{n}-U_{n-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5aa2e6499187089b9fd1c084decabb4b82b10920)
![{\displaystyle V_{0}=2,V_{1}=4,V_{n+1}=4V_{n}-V_{n-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dfd2f0d3b53e983547107746e5cc9b30bbe8783f)
Такі властивості доводяться по індукції:
![{\displaystyle V_{n}=U_{n+1}-U_{n-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/855fd6f2f17b9a916e312db7edb37999de5fc557)
![{\displaystyle U_{n}={\tfrac {1}{\sqrt {12}}}((2+{\sqrt {3}})^{n}-(2-{\sqrt {3}})^{n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d37012c59782108209d1dbf8f349bc0e83684ac4)
![{\displaystyle V_{n}=(2+{\sqrt {3}})^{n}+(2-{\sqrt {3}})^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49e3c50477149b181ea2e032f5adb88eface1c20)
![{\displaystyle U_{m+n}=U_{m}U_{n+1}-U_{m-1}U_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3241a62258985200c9b8584ac46f56b7f58e7e18)
Лема: Нехай
— просте і
, тоді справедливе наступне твердження.
Якщо
, то
.
Доказ леми: Покладемо
,
. Використовуємо вище описані властивості, щоб отримати значення для
і
:
, в той час як
.
Тим же способом отримаємо:
і ![{\displaystyle U_{3n+1}=U_{2n+1}U_{n+1}-U_{2n}U_{n}\equiv {a}^{3}{\pmod {p^{e+1}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0c731ea4f9406b27a64b6180085a02ecc34a135)
Інакше кажучи,
і
,
звідки випливає твердження леми, якщо взяти
.
Далі, розкривається вираз послідовностей за формулою біному Ньютона:
![{\displaystyle U_{n}=\sum _{k}{\binom {n}{2k+1}}2^{n-2k-1}3^{k},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8fc7dfb0e6de44d343a83c64c8fc0fb5ce7b789)
![{\displaystyle V_{n}=\sum _{k}{\binom {n}{2k}}2^{n-2k+1}3^{k}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/522c594803ea0eac4e01f8f877747ffc90bffb70)
Тепер, якщо ми покладемо
, де
— просте число, більше 2, і врахуємо, що
кратне
за винятком тих випадків, коли
і
, ми отримаємо:
,
.
Якщо
теорема Ферма стверджує, що
. Тому
, тобто
. Якщо
, то
![{\displaystyle U_{p+1}=4U_{p}-U_{p-1}=4U_{p}+V_{p}-U_{p+1}\equiv {-U_{p+1}}{\pmod {p}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53a7dd1476e750cd260c1e58795e9a86750e90ba)
тобто
. У той же спосіб отримується результат, що
, якщо
. Отже доведено, що для будь-якого простого числа, існує ціле число
таке, що
.
Лема: Якщо
— додатне ціле число, і
— найменше число таке, що
, то ми маємо:
тоді і тільки тоді, коли
кратне
.
Доведення: Зауважимо, що послідовність
збігається з послідовністю
по модулю
, де число
взаємно просте з
, так як:
.
Доведення теореми: По індукції маємо
.
Більш того, з
слідує, що
. Звідси слід, що
і
не мають загальних непарних дільників. Якщо
, то для
і
можна записати:
![{\displaystyle U_{2^{q-1}}=U_{2^{q-2}}V_{2^{q-2}}\equiv 0{\pmod {2^{q}-1}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f73c5e79b31ecd5063c63951e848e66828c9dbd)
![{\displaystyle U_{2^{q-2}}\not \equiv 0{\pmod {2^{q}-1}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/36635f32ff61aae406b1776aeed18daceb0891a2)
Тепер, якщо
, то
повинно бути дільником числа
, але не повинно ділити
, тому
. Доведемо, що
. Нехай
. Числа
більше 3, так як
непарне і виконується
,
— просте за умовою. Використовуючи раніше доведені леми, отримаємо
, де
![{\displaystyle t=\mathrm {lcm} ({p_{1}}^{e_{1}-1}(p_{1}+\varepsilon _{1}),\dots ,{p_{r}}^{e_{r}-1}(p_{r}+\varepsilon _{r}))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c961a6813e301f321cb5cbeafa3e7d1bbf45b60)
де
. Звідси випливає, що
кратне
. Покладемо
;
. Так як
— парне,
. Використовуємо раніше доведені факти і отримаємо
; отже
і
або
. Зауважимо, що
— ступінь двійки. Звідси випливає, що
і
. Якщо
— складене, то має бути
, де
і
— прості числа. Подальше розкладання на прості числа, якщо
— непарне, неможливо, тому
— просте.
Навпаки, припустимо, що
— просте. Покажемо, що
. Для цього достатньо показати, що
, так як
.
![{\displaystyle V_{2^{q}-1}=\left({\frac {{\sqrt {2}}+{\sqrt {6}}}{2}}\right)^{n+1}+\left({\frac {{\sqrt {2}}-{\sqrt {6}}}{2}}\right)^{n+1}=2^{-n}\sum _{k}{\binom {n+1}{2k}}{\sqrt {2}}^{n+1-2k}{\sqrt {6}}^{2k}=2^{(1-n)/2}\sum _{k}{\binom {n+1}{2k}}3^{k}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf9bf5d1e10adeb41a1650396ec5a5be312b3ce7)
Так як
— просте, то біноміальний коефіцієнт
ділиться на
крім тих випадків, коли
чи
. Отже:
.
Тут
, тому
за малої теореми Ферма. Нарешті, використовуючи найпростіший випадок квадратичного закону взаємності, покажемо, що
, так як
і
. Це значить, що
, так що
.
[3]
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
Для чисел виду
, де
існує модифікація цього тесту[en], розроблена Хансом Різелем[en]. Можливо узагальнення тесту для чисел виду
[4]. Також існує більш загальний варіант — тест Люка, який застосовний для будь-якого натурального числа
, якщо відоме розкладання на прості множники числа
.
Завдяки тесту Люка — Лемера прості числа Мерсенна утримують лідерство як найбільші відомі прості числа[5]. Саме тест Люка — Лемера лежить в основі проекту розподілених обчислень GIMPS, що шукає нові прості числа Мерсенна.