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

Тест Люка — Лемера — ефективний тест простоти для чисел Мерсенна. Завдяки цьому тесту найбільшими відомими простими числами завжди були прості числа Мерсенна, причому навіть до появи комп'ютерів.

Історія

Тест був запропонований французьким математиком Люка 1878 року і доповнений американським математиком Лемером 1930 року. Отриманий тест носить ім'я двох вчених, які спільно відкрили його, навіть не зустрічаючись за життя. 1952 року Робінсон за підтримки Лемера провів обчислення на комп'ютері SWAC з використанням тесту Люка — Лемера, результатом якого стало відкриття простих чисел $M_{521}$ і $M_{607}$. Пізніше того ж року були відкриті $M_{1279}$, $M_{2203}$ і $M_{2281}$.

Тест

Тест Люка — Лемера базується на тому спостереженні, що простота числа Мерсенна $M_{q}=2^{q}-1$ тягне простоту числа $q$, і в наступному твердженні:

Нехай $q$ — просте число, причому $q\geqslant {3}$. визначимо послідовність $L_{n}$ таким чином: $L_{0}=4,$ $L_{n+1}={L_{n}}^{2}-2.$ Тоді $M_{q}$ — просте тоді і тільки тоді, коли $L_{q-2}\equiv 0{\pmod {M_{q}}}$.

Для встановлення простоти $M_{p}$ послідовність чисел $L_{0},L_{2},\ldots ,L_{q-2}$ обчислюється по модулю числа $M_{q}$ (тобто обчислюються не власне числа $L_{k}$, довжина яких росте експоненціально, а остачі від ділення $L_{k}$ на $M_{q}$, довжина яких обмежена p бітами). Останнє число в цій послідовності $L_{q-2}{\bmod {M}}_{q}$ називається вирахуванням Люка — Лемера. Таким чином, число Мерсенна $M_{q}$ є простим тоді і тільки тоді, коли число $q$ просте, і вирахування Люка — Лемера дорівнює нулю.

Можливими значеннями $L_{0}$ є: 4, 10, 52, 724, 970, 10084, …

Обчислювальна складність

Обчислювальна складність тесту для числа $M_{q}=2^{q}-1$ дорівнює $O(q^{3})$, оскільки в процесі тесту виконується $O(q)$ піднесення до квадрату та вирахувань по модулю $M_{q}$. Довжина $M_{q}$ становить $q$ біт, причому найпростіший алгоритм множення чисел має складність $O(q^{2})$. Для прискорення тесту слід використовувати алгоритми швидкого множення великих цілих чисел, наприклад, алгоритм Шьонхаге — Штрассена. Складність тесту в такому випадку становитиме $O(q^{2}\log {q}\log {\log {q}})$.

Приклади

Розглянемо виконання тесту для числа Мерсенна $M_{13}=8191$.

$L_{0}=4$

$L_{1}=4^{2}-2\mod {8191}=14$

$L_{2}=14^{2}-2\mod {8191}=194$

$L_{3}=194^{2}-2\mod {8191}=4870$

$L_{4}=4870^{2}-2\mod {8191}=3953$

$L_{5}=3953^{2}-2\mod {8191}=5970$

$L_{6}=5970^{2}-2\mod {8191}=1857$

$L_{7}=1857^{2}-2\mod {8191}=36$

$L_{8}=36^{2}-2\mod {8191}=1294$

$L_{9}=1294^{2}-2\mod {8191}=3470$

$L_{10}=3470^{2}-2\mod {8191}=128$

$L_{11}=128^{2}-2\mod {8191}=0$

Отже, число $M_{13}=8191$ — просте.

Доведення

Теорема: Нехай $q$ — просте число, причому $q\geqslant {3}$. Визначимо послідовність $L_{n}$ таким чином:

$L_{0}=4,$

$L_{n+1}=({L_{n}}^{2}-2)\mod (2^{q}-1).$

Тоді $2^{q}-1$ — просте тоді і тільки тоді, коли $L_{q-2}=0$.

Доведення теореми засновано на властивостях послідовностей Люка $U_{n}=U_{n}(4,1)$ і $V_{n}=V_{n}(4,1)$:

$U_{0}=0,U_{1}=1,U_{n+1}=4U_{n}-U_{n-1}$

$V_{0}=2,V_{1}=4,V_{n+1}=4V_{n}-V_{n-1}$

Такі властивості доводяться по індукції:

$V_{n}=U_{n+1}-U_{n-1}$

$U_{n}={\tfrac {1}{\sqrt {12}}}((2+{\sqrt {3}})^{n}-(2-{\sqrt {3}})^{n})$

$V_{n}=(2+{\sqrt {3}})^{n}+(2-{\sqrt {3}})^{n}$

$U_{m+n}=U_{m}U_{n+1}-U_{m-1}U_{n}$

Лема: Нехай $p$ — просте і $e\geqslant 1$, тоді справедливе наступне твердження. Якщо $U_{n}\equiv 0{\pmod {p^{e}}}$, то $U_{np}\equiv 0{\pmod {p^{e+1}}}$.

Доказ леми: Покладемо $U_{n}=bp^{e}$, $U_{n+1}=a$. Використовуємо вище описані властивості, щоб отримати значення для $U_{2n}$ і $U_{2n+1}$:

$U_{2n}=bp^{e}(2a-4bp^{e})\equiv 2aU_{n}{\pmod {p^{e+1}}}$, в той час як $U_{2n+1}=U_{n+1}^{2}-U_{n}^{2}\equiv {a}^{2}{\pmod {p^{e+1}}}$.

Тим же способом отримаємо:

$U_{3n}=U_{2n+1}U_{n}-U_{2n}U_{n-1}\equiv (3a^{2})U_{n}{\pmod {p^{e+1}}}$ і $U_{3n+1}=U_{2n+1}U_{n+1}-U_{2n}U_{n}\equiv {a}^{3}{\pmod {p^{e+1}}}.$

Інакше кажучи,

$U_{kn}\equiv (ka^{k-1})U_{n}{\pmod {p^{e+1}}}$ і $U_{kn+1}\equiv {a^{k}}{\pmod {p^{e+1}}}$,

звідки випливає твердження леми, якщо взяти $k=p$.

Далі, розкривається вираз послідовностей за формулою біному Ньютона:

$U_{n}=\sum _{k}{\binom {n}{2k+1}}2^{n-2k-1}3^{k},$

$V_{n}=\sum _{k}{\binom {n}{2k}}2^{n-2k+1}3^{k}.$

Тепер, якщо ми покладемо $n=p$, де $p$ — просте число, більше 2, і врахуємо, що ${\tbinom {n}{k}}$ кратне $p$ за винятком тих випадків, коли $k=0$ і $k=n$, ми отримаємо:

$U_{p}\equiv 3^{(p-1)/2}{\pmod {p}}$, $V_{p}\equiv 4{\pmod {p}}$.

Якщо $p\neq 3$ теорема Ферма стверджує, що $3^{p-1}\equiv 1{\pmod {p}}$. Тому $(3^{(p-1)/2}-1)(3^{(p-1)/2}+1)\equiv 0{\pmod {p}}$, тобто $3^{(p-1)/2}\equiv \pm 1{\pmod {p}}$. Якщо $U_{p}\equiv {-1}{\pmod {p}}$, то

$U_{p+1}=4U_{p}-U_{p-1}=4U_{p}+V_{p}-U_{p+1}\equiv {-U_{p+1}}{\pmod {p}},$

тобто $U_{p+1}=0{\pmod {p}}$. У той же спосіб отримується результат, що $U_{p-1}=0{\pmod {p}}$, якщо $U_{p}=1$. Отже доведено, що для будь-якого простого числа, існує ціле число $\mid \varepsilon (p)\mid \leqslant 1$ таке, що $U_{p+\varepsilon (p)}=0{\pmod {p}}$.

Лема: Якщо $N$ — додатне ціле число, і $m=m(N)$ — найменше число таке, що $U_{m(N)}\equiv 0{\pmod {N}}$, то ми маємо:

$U_{n}\equiv 0{\pmod {N}}$ тоді і тільки тоді, коли $n$ кратне $m(N)$.

Доведення: Зауважимо, що послідовність $U_{n},U_{n+1},U_{n+2},...$ збігається з послідовністю $aU_{0},aU_{1},aU_{2},...$ по модулю $M$, де число $a=U_{m+1}\mod N$ взаємно просте з $N$, так як: $\gcd {(U_{n},U_{n+1})}=1$.

Доведення теореми: По індукції маємо

$L_{n}=V_{2^{n}}\mod (2^{q}-1)$.

Більш того, з $2U_{n+1}=4U_{n}+V_{n}$ слідує, що $\gcd {(U_{n},V_{n})}\leqslant 2$. Звідси слід, що $U_{n}$ і $V_{n}$ не мають загальних непарних дільників. Якщо $L_{q-2}=0$, то для $U_{2^{q-1}}$ і $U_{2^{q-2}}$ можна записати:

$U_{2^{q-1}}=U_{2^{q-2}}V_{2^{q-2}}\equiv 0{\pmod {2^{q}-1}}$

$U_{2^{q-2}}\not \equiv 0{\pmod {2^{q}-1}}$

Тепер, якщо $m=m(2^{q}-1)$, то $m$ повинно бути дільником числа $2^{q-2}$, але не повинно ділити $2^{q-2}$, тому $m=2^{q-1}$. Доведемо, що $n=2^{q}-1$. Нехай $n={p_{1}}_{1}^{e}...{p_{r}}_{r}^{e}$. Числа $p_{j}$ більше 3, так як $n$ непарне і виконується $n=2^{q}-1\equiv (-1)^{q}-1=-2{\pmod {3}}$, $q$ — просте за умовою. Використовуючи раніше доведені леми, отримаємо $U_{t}\equiv 0{\pmod {2^{q}-1}}$, де

$t=\mathrm {lcm} ({p_{1}}^{e_{1}-1}(p_{1}+\varepsilon _{1}),\dots ,{p_{r}}^{e_{r}-1}(p_{r}+\varepsilon _{r}))$

де $\varepsilon _{j}=\pm 1$. Звідси випливає, що $t$ кратне $m=2^{q}-1$. Покладемо $n_{0}=\prod _{j=1}^{r}{p_{j}}^{e_{j}-1}(p_{j}+\varepsilon _{j})$; $n_{0}\leqslant \prod _{j=1}^{r}{p_{j}}^{e_{j}-1}(p_{j}+1/5p_{j})=(6/5)^{r}n$. Так як $p_{j}+\varepsilon _{j}$ — парне, $t\leqslant {n_{0}}/2^{r-1}$. Використовуємо раніше доведені факти і отримаємо $m\leqslant {t}\leqslant 2(3/5)^{r}m<4(3/5)^{r}m<3m$; отже $r\leqslant 2$ і $t=m$ або $t=2m$. Зауважимо, що $t$ — ступінь двійки. Звідси випливає, що $e_{1}=1$ і $e_{r}=1$. Якщо $n$ — складене, то має бути $n=2^{q}-1=(2^{k}+1)(2^{l}-1)$, де $2^{k}+1$ і $2^{l}-1$ — прості числа. Подальше розкладання на прості числа, якщо $q$ — непарне, неможливо, тому $n$ — просте.

Навпаки, припустимо, що $n=2^{q}-1$ — просте. Покажемо, що $V_{2^{q}-2}\equiv 0{\pmod {n}}$. Для цього достатньо показати, що $V_{2^{q}-1}\equiv {-2}{\pmod {n}}$, так як $V_{2^{q}-1}=(V_{2^{q}-2}-2)^{2}$.

$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}.$

Так як $n$ — просте, то біноміальний коефіцієнт ${\tbinom {n+1}{2k}}={\tbinom {n}{2k}}+{\tbinom {n}{2k-1}}$ ділиться на $n$ крім тих випадків, коли $k=0$ чи $k=(n+1)/2$. Отже:

$2^{(n-1)/2}V_{2^{q}-1}\equiv {1+3^{(n+1)/2}}{\pmod {n}}$.

Тут $2\equiv (2^{(q+1)/2})^{2}{\pmod {n}}$, тому $2^{(n-1)/2}\equiv {(2^{(q+1)/2})}^{n-1}\equiv 1{\pmod {n}}$ за малої теореми Ферма. Нарешті, використовуючи найпростіший випадок квадратичного закону взаємності, покажемо, що $3^{(n-1)/2}\equiv {-1}{\pmod {n}}$, так як $n\mod {3}=1$ і $n\mod {4}=3$. Це значить, що $V_{2^{q}-1}\equiv {-2}$, так що $V_{2^{q}-2}\equiv 0$.

Псевдокод

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

Модифікації

Для чисел виду $k2^{n}-1$, де $2^{n}>k$ існує модифікація цього тесту, розроблена Хансом Різелем. Можливо узагальнення тесту для чисел виду $A2^{2n}+B2^{n}-1$. Також існує більш загальний варіант — тест Люка, який застосовний для будь-якого натурального числа $N$, якщо відоме розкладання на прості множники числа $N-1$.

Застосування

Завдяки тесту Люка — Лемера прості числа Мерсенна утримують лідерство як найбільші відомі прості числа. Саме тест Люка — Лемера лежить в основі проекту розподілених обчислень GIMPS, що шукає нові прості числа Мерсенна.

Див. також

• Тест простоти
• Тест простоти Люка
• Числа Мерсенна
• Тест Люка — Лемера — Різеля

Література

• Weisstein, Eric W. Lucas-Lehmer Test(англ.) на сайті Wolfram MathWorld.
• А.Н.Рудаков. Числа Фібоначчі і простота числа 2¹²⁷-1 // 4 (третя серія). — Математична просвіта, 2000.
• Donald E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. — Addison-Wesley Professional, 1997. — С. 389-394. — ISBN 978-0201896848.
• Paulo Ribenboim. The Little Book of Bigger Primes. — Springer, 2004. — С. 75-80. — ISBN 978-0387201696.
• Eric Bach; Jeffrey Shallit. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. — The MIT Press, 1996. — С. 273-275. — ISBN 978-0262024051.