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

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

Історія

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

Тест

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

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

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

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

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

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

Приклади

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

${\displaystyle L_{0}=4}$

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

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

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

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

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

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

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

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

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

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

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

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

Доведення

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

${\displaystyle L_{0}=4,}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Модифікації

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

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

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

Див. також

• Тест простоти
• Тест простоти Люка
• Числа Мерсенна
• ^[en]

Примітки

1. Paulo Ribenboim. The Little Book of Bigger Primes. — Springer. — 2004. — С. 78. — (2-ге видання) — .
2. Eric Bach; Jeffrey Shallit. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. — The MIT Press, 1996. — С. 275. — .
3. Donald E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. — Addison-Wesley Professional, 1997. — С. 2. — (2-ге видання) — .
4. H. C. Williams. A class of primality tests for trinomials which includes the Lucas-Lehmer test (англ.). Архів оригіналу за 23 грудня 2012. Процитовано 28 листопада 2012.
5. The «Top Ten» Record Primes(англ.).

Література

• 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. — .
• Paulo Ribenboim. The Little Book of Bigger Primes. — Springer, 2004. — С. 75-80. — .
• Eric Bach; Jeffrey Shallit. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. — The MIT Press, 1996. — С. 273-275. — .