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

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

Історія

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

Тест

Тест Люка — Лемера базується на тому спостереженні, що простота числа Мерсенна ${\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})}$[2], оскільки в процесі тесту виконується ${\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}$. [3]

Псевдокод

Lucas–Lehmer(p)
    var s = 4
    var M = 2^p — 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}$[4]. Також існує більш загальний варіант — тест Люка, який застосовний для будь-якого натурального числа ${\displaystyle N}$, якщо відоме розкладання на прості множники числа ${\displaystyle N-1}$.

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

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

Див. також

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

Примітки

1. Paulo Ribenboim. The Little Book of Bigger Primes. — Springer. — 2004. — С. 78. — (2-ге видання) — ISBN 978-0387201696.
2. Eric Bach; Jeffrey Shallit. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. — The MIT Press, 1996. — С. 275. — ISBN 978-0262024051.
3. Donald E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. — Addison-Wesley Professional, 1997. — С. 2. — (2-ге видання) — ISBN 978-0201896848.
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^127-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.