Перегляд вихідного коду сторінки Тест Люка — Лемера

'''Тест Люка&nbsp;— Лемера'''&nbsp;— ефективний [[тест простоти]] для [[число Мерсенна|чисел Мерсенна]]. Завдяки цьому тесту [[Найбільше відоме просте число|найбільшими відомими простими числами]] завжди були прості [[числа Мерсенна]], причому навіть до появи [[комп'ютер]]ів<ref name=Ribenboim>{{книга |автор= Paulo Ribenboim |назва= The Little Book of Bigger Primes| видання= Springer| серія=2-ге видання| рік=2004|сторінки = 78| isbn = 978-0387201696|ref = rib}}</ref>.

== Історія ==
Тест був запропонований французьким математиком [[Едуард Люка|Люка]] [[1878|1878 року]] і доповнений американським математиком {{Не перекладено|Деррік Генрі Лемер|Лемером|en|Derrick Henry Lehmer}} [[1930|1930 року]]. Отриманий тест носить ім'я двох вчених, які спільно відкрили його, навіть не зустрічаючись за життя. [[1952|1952 року]] [[Рафаель Робінсон|Робінсон]] за підтримки Лемера провів обчислення на комп'ютері [[SWAC]] з використанням тесту Люка&nbsp;— Лемера, результатом якого стало відкриття простих чисел <math>M_{521}</math> і <math>M_{607}</math>. Пізніше того ж року були відкриті <math>M_{1279}</math>, <math>M_{2203}</math> і <math>M_{2281}</math><ref name=Ribenboim/>.

== Тест ==
Тест Люка&nbsp;— Лемера базується на тому спостереженні, що простота числа Мерсенна <math>M_q = 2^q - 1</math> тягне простоту числа <math>q</math>, і в наступному твердженні:
{{рамка}}
Нехай <math>q</math>&nbsp;— [[просте число]], причому <math>q\geqslant{3}</math>. визначимо [[Послідовність (математика)|послідовність]] <math>L_n</math> таким чином:
: <math>L_0=4,</math>
: <math>L_{n+1}={L_n}^2-2.</math>
Тоді <math>M_q</math>&nbsp;— просте тоді і тільки тоді, коли <math>L_{q-2}\equiv 0\pmod{M_q}</math>.
{{/рамка}}

Для встановлення простоти <math>M_p</math> послідовність чисел <math>L_0, L_2, \ldots, L_{q-2}</math> обчислюється по [[Модуль числа|модулю числа]] <math>M_q</math> (тобто обчислюються не власне числа <math>L_k</math>, довжина яких росте експоненціально, а [[остача|остачі]] від ділення <math>L_k</math> на <math>M_q</math>, довжина яких обмежена ''p'' [[біт]]ами). Останнє число в цій послідовності <math>L_{q-2} \bmod M_q</math> називається '''вирахуванням Люка&nbsp;— Лемера'''. Таким чином, число Мерсенна <math>M_q</math> є простим тоді і тільки тоді, коли число <math>q</math> просте, і вирахування Люка&nbsp;— Лемера дорівнює нулю.

Можливими значеннями <math>L_0</math> є: 4, 10, 52, 724, 970, 10084, …

== Обчислювальна складність ==
[[Обчислювальна складність]] тесту для числа <math>M_q=2^{q}-1</math> дорівнює <math>O(q^3)</math><ref name='bach'>{{книга
|назва = Algorithmic Number Theory, Vol. 1: Efficient Algorithms
|автор = Eric Bach;  Jeffrey Shallit
|isbn = 978-0262024051
|сторінки = 275
|рік =  1996
|видавництво = The MIT Press
}}</ref>, оскільки в процесі тесту виконується <math>O(q)</math> піднесення до квадрату та вирахувань по модулю <math>M_q</math>. Довжина <math>M_q</math> становить <math>q</math> біт, причому найпростіший алгоритм множення чисел має складність <math>O(q^2)</math>. Для прискорення тесту слід використовувати алгоритми швидкого множення великих цілих чисел, наприклад, [[алгоритм Шьонхаге — Штрассена]]. Складність тесту в такому випадку становитиме <math>O(q^{2}\log{q}\log{\log{q}})</math>.

== Приклади ==
Розглянемо виконання тесту для [[число Мерсенна|числа Мерсенна]] <math>M_{13}=8191</math>.
: <math>L_0=4</math>
: <math>L_1=4^2-2\mod{8191} = 14</math>
: <math>L_2=14^2-2\mod{8191}=194</math>
: <math>L_3=194^2-2\mod{8191}=4870</math>
: <math>L_4=4870^2-2\mod{8191}=3953</math>
: <math>L_5=3953^2-2\mod{8191}=5970</math>
: <math>L_6=5970^2-2\mod{8191}=1857</math>
: <math>L_7=1857^2-2\mod{8191}=36</math>
: <math>L_8=36^2-2\mod{8191}=1294</math>
: <math>L_9=1294^2-2\mod{8191}=3470</math>
: <math>L_{10}=3470^2-2\mod{8191}=128</math>
: <math>L_{11}=128^2-2\mod{8191}=0</math>
Отже, число <math>M_{13}=8191</math>&nbsp;— просте.

== Доведення ==
'''Теорема:''' Нехай <math>q</math>&nbsp;— просте число, причому <math>q\geqslant{3}</math>. Визначимо послідовність <math>L_n</math> таким чином:
: <math>L_0=4,</math>
: <math>L_{n+1}=({L_n}^2-2) \mod (2^q-1).</math>
Тоді <math>2^q-1</math>&nbsp;— просте тоді і тільки тоді, коли <math>L_{q-2}=0</math>.

Доведення теореми засновано на властивостях [[Послідовність Люка|послідовностей Люка]] <math>U_n=U_n(4,1)</math> і <math>V_n=V_n(4,1)</math>:
: <math>U_0 = 0, U_1 = 1, U_{n+1} = 4U_{n} - U_{n-1}</math>
: <math>V_0 = 2, V_1 = 4, V_{n+1} = 4V_{n} - V_{n-1}</math>
Такі властивості доводяться по [[Математична індукція|індукції]]:
: <math>V_{n} = U_{n+1} - U_{n-1}</math>
: <math>U_{n} = \tfrac{1}{\sqrt{12}}((2 + \sqrt{3})^{n} - (2 - \sqrt{3})^{n})</math>
: <math>V_{n} = (2 + \sqrt{3})^{n} + (2 - \sqrt{3})^{n} </math>
: <math>U_{m+n} = U_{m}U_{n+1} - U_{m-1}U_{n}</math>

'''Лема:''' Нехай <math>p</math>&nbsp;— просте і <math>e \geqslant 1</math>, тоді справедливе наступне твердження.
Якщо <math>U_{n}\equiv0\pmod{p^e}</math>, то <math>U_{np}\equiv0\pmod{p^{e+1}}</math>.

'''Доказ леми:''' Покладемо <math>U_{n}=bp^e</math>, <math>U_{n+1}=a</math>. Використовуємо вище описані властивості, щоб отримати значення для <math>U_{2n}</math> і <math>U_{2n+1}</math>:
: <math>U_{2n}=bp^{e}(2a-4bp^e)\equiv2aU_{n}\pmod{p^{e+1}}</math>, в той час як <math>U_{2n+1}=U_{n+1}^2-U_{n}^2\equiv{a}^2\pmod{p^{e+1}}</math>.

Тим же способом отримаємо:
: <math>U_{3n}=U_{2n+1}U_{n}-U_{2n}U_{n-1}\equiv(3a^2)U_{n}\pmod{p^{e+1}}</math> і <math>U_{3n+1}=U_{2n+1}U_{n+1}-U_{2n}U_{n}\equiv{a}^3\pmod{p^{e+1}}.</math>
Інакше кажучи,
: <math>U_{kn}\equiv(ka^{k-1})U_{n}\pmod{p^{e+1}}</math> і <math>U_{kn+1}\equiv{a^k}\pmod{p^{e+1}}</math>,
звідки випливає твердження леми, якщо взяти <math>k=p</math>.

Далі, розкривається вираз послідовностей за формулою [[Біном Ньютона|біному Ньютона]]:
: <math>U_{n}=\sum_{k} \binom{n}{2k+1}2^{n-2k-1}3^{k},</math>
: <math>V_{n}=\sum_{k} \binom{n}{2k}2^{n-2k+1}3^{k}.</math>
Тепер, якщо ми покладемо <math>n=p</math>, де <math>p</math>&nbsp;— просте число, більше 2, і врахуємо, що <math>\tbinom{n}{k}</math> кратне <math>p</math> за винятком тих випадків, коли <math>k=0</math> і <math>k=n</math>, ми отримаємо:
: <math>U_{p}\equiv3^{(p-1)/2}\pmod{p}</math>, <math>V_p\equiv4\pmod{p}</math>.
Якщо <math>p\neq3</math> [[Мала теорема Ферма|теорема Ферма]] стверджує, що <math>3^{p-1}\equiv1\pmod{p}</math>. Тому <math>(3^{(p-1)/2}-1)(3^{(p-1)/2}+1)\equiv0\pmod{p}</math>, тобто <math>3^{(p-1)/2}\equiv\pm1\pmod{p}</math>. Якщо <math>U_{p}\equiv{-1}\pmod{p}</math>, то
: <math>U_{p+1}=4U_{p}-U_{p-1}=4U_{p}+V_{p}-U_{p+1}\equiv{-U_{p+1}}\pmod{p},</math>
тобто <math>U_{p+1}=0\pmod{p}</math>. У той же спосіб отримується результат, що <math>U_{p-1}=0\pmod{p}</math>, якщо <math>U_{p}=1</math>. Отже доведено, що для будь-якого простого числа, існує ціле число <math>\mid\varepsilon(p)\mid\leqslant1</math> таке, що <math>U_{p+\varepsilon(p)}=0\pmod{p}</math>.

'''Лема:''' Якщо <math>N</math>&nbsp;— додатне ціле число, і <math>m=m(N)</math>&nbsp;— найменше число таке, що <math>U_{m(N)}\equiv 0\pmod{N}</math>, то ми маємо:
: <math>U_n\equiv 0\pmod{N}</math> тоді і тільки тоді, коли <math>n</math> кратне <math>m(N)</math>.

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

'''Доведення теореми''': По індукції маємо
: <math>L_n=V_{2^n}\mod (2^q-1)</math>.
Більш того, з <math>2U_{n+1}=4U_n+V_n</math> слідує, що <math>\gcd{(U_n,V_n)}\leqslant 2</math>. Звідси слід, що <math>U_n</math> і <math>V_n</math> не мають загальних непарних дільників. Якщо <math>L_{q-2}=0</math>, то для <math>U_{2^{q-1}}</math> і <math>U_{2^{q-2}}</math> можна записати:
: <math>U_{2^{q-1}}=U_{2^{q-2}}V_{2^{q-2}}\equiv0\pmod{2^q-1}</math>
: <math>U_{2^{q-2}}\not\equiv0\pmod{2^q-1}</math>
Тепер, якщо <math>m=m(2^q-1)</math>, то <math>m</math> повинно бути дільником числа <math>2^{q-2}</math>, але не повинно ділити <math>2^{q-2}</math>, тому <math>m=2^{q-1}</math>. Доведемо, що <math>n=2^{q}-1</math>. Нехай <math>n={p_1}^e_1...{p_r}^e_r</math>. Числа <math>p_j</math> більше 3, так як <math>n</math> непарне і виконується <math>n=2^q-1\equiv (-1)^q-1=-2\pmod{3}</math>, <math>q</math>&nbsp;— просте за умовою. Використовуючи раніше доведені леми, отримаємо <math>U_t\equiv0\pmod{2^q-1}</math>, де
: <math>t=\mathrm{lcm}({p_1}^{e_1-1}(p_1+\varepsilon_1),\dots,{p_r}^{e_r-1}(p_r+\varepsilon_r))</math>
де <math>\varepsilon_j=\pm1</math>. Звідси випливає, що <math>t</math> кратне <math>m=2^q-1</math>. Покладемо <math>n_0=\prod^r_{j=1}{p_j}^{e_j-1}(p_j+\varepsilon_j)</math>; <math>n_0\leqslant\prod^r_{j=1}{p_j}^{e_j-1}(p_j+1/5p_j)=(6/5)^rn</math>. Так як <math>p_j+\varepsilon_j</math>&nbsp;— парне, <math>t\leqslant{n_0}/2^{r-1}</math>. Використовуємо раніше доведені факти і отримаємо <math>m\leqslant{t}\leqslant2(3/5)^{r}m<4(3/5)^rm<3m</math>; отже <math>r\leqslant 2</math> і <math>t=m</math> або <math>t=2m</math>. Зауважимо, що <math>t</math>&nbsp;— ступінь двійки. Звідси випливає, що <math>e_1=1</math> і <math>e_r=1</math>. Якщо <math>n</math>&nbsp;— складене, то має бути <math>n=2^q-1=(2^k+1)(2^l-1)</math>, де <math>2^k+1</math> і <math>2^l-1</math>&nbsp;— прості числа. Подальше розкладання на прості числа, якщо <math>q</math>&nbsp;— непарне, неможливо, тому <math>n</math>&nbsp;— просте.

Навпаки, припустимо, що <math>n=2^q-1</math>&nbsp;— просте. Покажемо, що <math>V_{2^q-2}\equiv0\pmod{n}</math>. Для цього достатньо показати, що <math>V_{2^q-1}\equiv{-2}\pmod{n}</math>, так як <math>V_{2^q-1}=(V_{2^q-2}-2)^2</math>.
: <math>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.</math>
Так як <math>n</math>&nbsp;— просте, то біноміальний коефіцієнт <math>\tbinom{n+1}{2k}=\tbinom{n}{2k}+\tbinom{n}{2k-1}</math> ділиться на <math>n</math> крім тих випадків, коли <math>k=0</math> чи <math>k=(n+1)/2</math>. Отже:
: <math>2^{(n-1)/2}V_{2^q-1}\equiv{1+3^{(n+1)/2}}\pmod{n}</math>.
Тут <math>2\equiv(2^{(q+1)/2})^2\pmod{n}</math>, тому <math>2^{(n-1)/2}\equiv{(2^{(q+1)/2})}^{n-1}\equiv1\pmod{n}</math> за [[Мала теорема Ферма|малої теореми Ферма]]. Нарешті, використовуючи найпростіший випадок [[Квадратичний закон взаємності|квадратичного закону взаємності]], покажемо, що <math>3^{(n-1)/2}\equiv{-1}\pmod{n}</math>, так як <math>n\mod{3}=1</math> і <math>n\mod{4}=3</math>. Це значить, що <math>V_{2^q-1}\equiv{-2}</math>, так що <math>V_{2^q-2}\equiv0</math>.
<ref>{{книга   
|автор = Donald E. Knuth    
|назва = The Art of Computer Programming, Volume 2: Seminumerical Algorithms   
|серія= 2-ге видання   
|видавництво = Addison-Wesley Professional
|рік = 1997  
|сторінки = 2   
|сторінок = 392   
|isbn = 978-0201896848  
}}</ref>

== Псевдокод ==
 '''Lucas–Lehmer'''(''p'')
     '''var''' ''s'' = 4
     '''var''' ''M'' = 2<sup>''p''</sup> — 1
     '''repeat''' ''p'' — 2 times:
         ''s'' = ((''s'' &times; ''s'') — 2) mod ''M''
     '''if''' ''s'' = 0 '''return''' PRIME '''else''' '''return''' COMPOSITE

== Модифікації ==
Для чисел виду <math>k2^n-1</math>, де <math>2^n>k</math> існує {{Не перекладено|тест Люка — Лемера — Різеля|модифікація цього тесту|en|Lucas–Lehmer–Riesel test}}, розроблена {{iw|Hans Riesel|Хансом Різелем}}. Можливо узагальнення тесту для чисел виду <math>A2^{2n}+B2^{n}-1</math><ref>{{cite web|url= http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.pjm/1102734270|title= A class of primality tests for trinomials which includes the Lucas-Lehmer test.|author= H. C. Williams|date= |work= |publisher= |accessdate= 2012-11-28|language= en|archiveurl= https://www.webcitation.org/6D71yxG0X?url=http://projecteuclid.org/DPubS?service=UI|archivedate= 2012-12-23|deadurl= no}}</ref>. Також існує більш загальний варіант&nbsp;— [[Тест простоти|тест Люка,]] який застосовний для будь-якого [[Натуральне число|натурального числа]] <math>N</math>, якщо відоме розкладання на прості множники числа <math>N-1</math>.

== Застосування ==
Завдяки тесту Люка&nbsp;— Лемера прості числа Мерсенна утримують лідерство як найбільші відомі прості числа<ref>[http://primes.utm.edu/largest.html#biggest The «Top Ten» Record Primes]{{ref-en}}.</ref>. Саме тест Люка&nbsp;— Лемера лежить в основі проекту [[розподілені обчислення|розподілених обчислень]] [[GIMPS]], що шукає нові прості числа Мерсенна.

== Див. також ==
* [[Тест простоти]]
* [[Тест простоти Люка]]
* [[Числа Мерсенна]]
* {{Не перекладено|Тест Люка — Лемера — Різеля||en|Lucas–Lehmer–Riesel test}}

== Примітки ==
{{примітки}}

== Література ==
* {{MathWorld|Lucas-LehmerTest|Lucas-Lehmer Test}}
* {{стаття |автор= А.Н.Рудаков |заголовок= Числа Фібоначчі і простота числа 2<sup>127</sup>-1 |видавництво= Математична просвіта |видання= 4 (третя серія) |рік= 2000 |посилання= http://www.mccme.ru/free-books/matpros5.html}}
* {{книга |автор= Donald E. Knuth |заголовок= The Art of Computer Programming, Volume 2: Seminumerical Algorithms| видавництво= Addison-Wesley Professional| випуск= 3 видання| рік=1997|сторінки= 389-394|isbn = 978-0201896848|ref = knuth}}
* {{книга |автор= Paulo Ribenboim |заголовок= The Little Book of Bigger Primes| видавництво= Springer| випуск=2-ге видання| рік=2004|сторінки= 75-80| isbn = 978-0387201696|ref = rib}}
* {{книга
|заголовок = Algorithmic Number Theory, Vol. 1: Efficient Algorithms
|автор= Eric Bach;  Jeffrey Shallit
|isbn = 978-0262024051
|сторінки = 273-275
|рік =  1996
|видавництво = The MIT Press
}}

{{Алгоритми теорії чисел}}

[[Категорія:Тести простоти]]