uk %D0%A2%D0%B5%D1%81%D1%82 %D0%9B%D1%8E%D0%BA%D0%B0 %E2%80%94 %D0%9B%D0%B5%D0%BC%D0%B5%D1%80%D0%B0

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

Історія

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

Тест

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

Модифікації

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

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

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

Див. також

Примітки

↑ ^а ^б Paulo Ribenboim. The Little Book of Bigger Primes. — Springer. — 2004. — С. 78. — (2-ге видання) — ISBN 978-0387201696.
↑ Eric Bach; Jeffrey Shallit. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. — The MIT Press, 1996. — С. 275. — ISBN 978-0262024051.
↑ Donald E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. — Addison-Wesley Professional, 1997. — С. 2. — (2-ге видання) — ISBN 978-0201896848.
↑ H. C. Williams. A class of primality tests for trinomials which includes the Lucas-Lehmer test (англ.). Архів оригіналу за 23 грудня 2012. Процитовано 28 листопада 2012.
↑ 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. — 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.

[Ribenboim-1] а ^б Paulo Ribenboim. The Little Book of Bigger Primes. — Springer. — 2004. — С. 78. — (2-ге видання) — ISBN 978-0387201696.

[bach-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(англ.).

[1]

[2]

[3]

[4]

[5]