Luc-Lehmerův test

Lucas-Lehmer test ( angl. Lucas -Lehmer test , zkr. LLT ) je polynomiální , deterministický a nepodmíněný (tj. nezávislý na neprokázaných hypotézách) test primality pro Mersennova čísla . Formuloval Édouard Lucas v roce 1878 a dokázal Lemaire v roce 1930 .

Dané prvočíslo počítá s polynomiálním časem bitové délky Mersennova čísla k určení, zda je prvočíslo nebo složené . Důkaz platnosti testu se do značné míry opírá o Lucasovy funkce , které umožnily zobecnit Lucas-Lehmerův test na některá čísla, jejichž tvar je odlišný od Mersennových čísel . $p>2$ $p$ $M_{p}=2^{p}-1$ $M_{p}$

Díky tomuto testu byla největší známá prvočísla téměř vždy Mersennova prvočísla, dokonce ještě před příchodem počítačů ; je to on, kdo stojí za projektem distribuovaných počítačů GIMPS , který se zabývá hledáním nových Mersennových prvočísel. Zajímavý je také spojením se sudými čísly .

Formulace

Test je založen na následujících kritériích jednoduchosti Mersennových čísel [1] :

Nechť je jednoduché liché číslo. Mersennovo číslo je prvočíslo právě tehdy, když dělí tý člen posloupnosti $p$ $M_{p}=2^{p}-1$ $(p-1)$

4,\;14,\;194,\;37634,\;\ldots

[2] ,

dáno rekurzivně : $S_{k}={\begin{cases}4&k=1,\\S_{k-1}^{2}-2&k>1.\end{cases))$

Lemaire , 1930

Pro kontrolu jednoduchosti se posloupnost čísel počítá modulo the number (tedy nepočítají se samotná čísla , jejichž délka roste exponenciálně , ale zbytky po dělení , jejichž délka je omezena bity ). Poslední číslo v této sekvenci se nazývá Lucas-Lehmerův zbytek [3] . Mersennovo číslo je tedy prvočíslo právě tehdy, když je toto číslo liché prvočíslo a Lucas-Lehmerův zbytek je nula. Samotný algoritmus lze zapsat jako pseudokód [4] : $M_{p}$ ${\displaystyle S_{1},S_{2},\ldots ,S_{p-1))$ $M_{p}$ $S_k$ $S_k$ $M_{p}$ $p$ $S_{p-1}{\bmod {M}}_{p}$ $M_{p}$ $p$

LLT (p) ►Vstup: liché prvočíslo p S=4 k = 1 M = 2 p − 1 Dokud k != p - 1 S = ((S × S) − 2) mod M k += 1 Konec smyčky Pokud S = 0 proveďte Return SIMPLE jinak Return COMPOUND Koncová podmínka

Hodnoty , pro které platí kritérium primality, tvoří sekvenci: [5] [6] [7] . $S_{1}$ $4,\;10,\;52,\;724,\;970,\;10084,\;\ldots$

Není nutné kontrolovat všechna prvočísla lichá čísla v přímém výčtu, protože některá Mersennova čísla speciálního tvaru jsou vždy složená, což vyplývá například z následující věty dokázané Eulerem [ 8] : $p$

Jsou-li čísla a prvočísla, pak . $p=4n+3$ $q=2p+1=8n+7$ $M_{p}\equiv 0{\pmod {q))$

Důkaz

Jeden přístup k důkazu je založen na použití Lukeových funkcí :

V_{n}(P,Q)=\alpha ^{n}+\beta ^{n},

U_{n}(P,Q)={\frac {\alpha ^{n}-\beta ^{n)){\alpha -\beta )),

kde jsou kořeny kvadratické rovnice $\alpha ,\;\beta$

x^{2}-Px+Q=0

s diskriminantem a a jsou coprime . $D=P^{2}-4Q,$ $P$ $Q$

V důkazu jsou použity zejména některé vlastnosti těchto funkcí, konkrétně [9] :

jeden.

V_{n}^{2}-DU_{n}^{2}=4Q^{n}

{\displaystyle V_{2n}=V_{n}^{2}-2Q^{n},\quad U_{2n}=U_{n}V_{n))

{\frac {V_{n}+{\sqrt {D}}U_{n}}{2}}=\left({\frac {P+{\sqrt {D}}}{2}}\ správně)^{n}

4. Pokud , , a

P'\equiv P{\pmod {N}}

Q'\equiv Q{\pmod {N))

(Q,N)=1

QP'=P^{2}-2Q{\pmod {N}}

, pak

{\begin{cases}Q^{n}V_{n}(P',1)\equiv V_{2n}(P,Q){\pmod {N}}\\PQ^{n-1 }U_{n}(P',1)\ekviv U_{2n}(P,Q){\pmod {N}}\end{cases}}

5. Jestliže je prvočíslo, takové, že coprime s , pak dělí ,

p

2DQ

p

p

U_{\Phi (p)} (P,Q)

kde , a je Legendre symbol .

\Phi (p)=p-\left({\frac {D}{p}}\right)

\left({\frac {D}{p}}\right)

Důkazní schéma [9] :

Nutnost

Z vlastnosti 4. modulo for , vyplývá: $N=M_{p}$ $P=2$ $Q=-2$

2^{n}V_{n}(-4,1)\equiv V_{2n}(2,-2){\pmod {N))

a podle majetku 2.

V_{2n}(-4,1)=V_{n}^{2}(-4,1)-2

proto

S_{p-1}\equiv V_{\frac {N+1}{4}}(-4,1){\pmod {N}}

V_{\frac {N+1}{2}}(2,-2)\equiv 2^{\frac {N+1}{4}}S_{p-1}{\pmod {N} }

$D=2^{2}-4\cdot (-2)=12$ , takže pokud je prvočíslo, pak se také dělí od posledních dvou vlastností $N$ $\left({\frac {D}{N}}\right)=-1$ $N$

U_{N+1}(2,-2)=V_{\frac {N+1}{2}}(2,-2)U_{\frac {N+1}{2}}(2 ,-2)

Dále z vlastností 1. a 2.

V_{N+1}=V_{\frac {N+1}{2}}^{2}-2\cdot (-2)^{\frac {N+1}{2}}\equiv 8+4=12{\pmod {N}}

ale podle majetku 3.

V_{N+1}\equiv 2(1+{\sqrt {3)))^{N+1}=2(1+{\sqrt {3)))(1+3^{\frac {N-1}{2}}{\sqrt {3}}\equiv 2(1-3)=-4{\pmod {N}}

to je, rozděluje , a proto . $N$ $V_{\frac {N+1}{2}}(2,-2)$ $S_{p-1}$

Dostatečnost

Pokud rozděluje , pak z důkazu nutnosti vyplývá , že rozděluje a . spoluvlastní se podle vlastnosti 1. a podle vlastnosti 2. - dělí . Ale pak každý prvočíselník čísla může být reprezentován jako , tedy prvočíslo. $N$ $S_{p-1}$ $V_{\frac {N+1}{2}}$ $N$ $U_{\frac {N+1}{2))$ $U_{N+1}$ $N$ $\pm 1+k2^{p}>{\sqrt {N))$ $N=M_{p}$

Historie

Kritérium jednoduchosti navrhl francouzský matematik Lucas v roce 1878 . Zejména Lucas ukázal, že algoritmus umožňuje testování prvočísel pro prvočísla [9] . V roce 1930 americký matematik Lehmer plně prokázal platnost kritéria pro všechna lichá prvočísla ve své disertační práci pro titul doktora filozofie [1] . $M_{p}$ $p\equiv 1{\pmod {4}}$ $p$

V roce 1952 provedl Robinson s podporou Lemaire výpočty na počítači SWAC pomocí Luc-Lehmerova testu, který vyústil v objev prvočísel a . Později ve stejném roce byly objeveny , a [10] . $M_{{521}}$ $M_{{607}}$ $M_{{1279}}$ $M_{{2203}}$ $M_{{2281}}$

Snadná implementace testu a růst výpočetního výkonu počítačů umožnil prakticky komukoli hledat Mersennova prvočísla. Takže v roce 1978 dva američtí středoškoláci Laura Nickel a Kurt Knoll (Lemaire je naučil teorii čísel) prokázali jednoduchost čísel za 3 roky práce pomocí superpočítače CDC Cyber 176 na University of California [11] . $M_{21701}$

Největší známé Mersennovo prvočíslo pro rok 2018 získané pomocí Lucas-Lehmerova testu je . $M_{82589933}$

Příklady

Požadavek na zvláštnost v podmínce kritéria je zásadní, protože je jednoduchý , ale . $p$ $M_{2}=2^{2}-1=3$ $S_{1}\equiv 4{\pmod {3}}=1\není =0$

Číslo je prvočíslo [13] . Opravdu, $M_{13}=2^{13}-1=8191$

S_{1}=4

S_{2}\equiv 4^{2}-2{\pmod {8191}}=14

S_{3}\equiv 14^{2}-2{\pmod {8191}}=194

S_{4}\equiv 194^{2}-2{\pmod {8191}}=4870

S_{5}\equiv 4870^{2}-2{\pmod {8191}}=3953

S_{6}\equiv 3953^{2}-2{\pmod {8191}}=5970

S_{7}\equiv 5970^{2}-2{\pmod {8191}}=1857

S_{8}\equiv 1857^{2}-2{\pmod {8191}}=36

S_{9}\equiv 36^{2}-2{\pmod {8191}}=1294

S_{10}\equiv 1294^{2}-2{\pmod {8191}}=3470

S_{11}\equiv 3470^{2}-2{\pmod {8191}}=128

S_{12}\equiv 128^{2}-2{\pmod {8191}}=0

Použití testu na číslo ukazuje, že je složené [13] : $M_{11}=2^{11}-1=2047$

S_{1}=4

S_{2}\equiv 4^{2}-2{\pmod {2047}}=14

S_{3}\equiv 14^{2}-2{\pmod {2047}}=194

S_{4}\equiv 194^{2}-2{\pmod {2047}}=788

S_{5}\equiv 788^{2}-2{\pmod {2047}}=701

S_{6}\equiv 701^{2}-2{\pmod {2047}}=119

S_{7}\equiv 119^{2}-2{\pmod {2047}}=1877

S_{8}\equiv 1877^{2}-2{\pmod {2047}}=240

S_{9}\equiv 240^{2}-2{\pmod {2047}}=282

S_{10}\equiv 282^{2}-2{\pmod {2047}}=1736\not =0

Opravdu, . $2047=23\cdot 89$

Výpočetní složitost

V uvažovaném testu jsou dvě hlavní operace: kvadratura a dělení modulo . Efektivní algoritmus pro modulo a Mersennovo číslo na počítači (ve skutečnosti redukující na operace s několika bitovým posunem ) je dán následující větou [4] :

Pro celé číslo a Mersennovo číslo nastává modulová kongruence $X$ $M_{p}=2^{p}-1$

x\equiv \left(x{\bmod {2}}^{p}\right)+\left\lfloor {\frac {x}{2^{p}}}\right\rfloor {\pmod {M_{p}}}

navíc násobení modulem je ekvivalentní levému cyklickému posunu o bit (jestliže , pak se posun provede v opačném směru). $2^k$ $M_{p}$ $k$ $k<0$

Chcete-li například vypočítat zbytek po dělení čísla číslem , musíte převést původní číslo do binárního tvaru: a podle věty se rozdělit na dvě části pokaždé, když překročí : $x=916$ $M_{5}=2^{5}-1=31$ ${\displaystyle 916={1110010100}_{2))$ $X$ $M_{5}$

{\begin{aligned}916{\bmod {2}^{5}-1&\equiv \left(916{\bmod {2}}^{5}\right)+\left\lfloor {\ frac {916}{2^{5}}}\pravé\rpodlaží {\pmod {2^{5}-1}}\\&\equiv {10100}_{2}+{11100}_{2}{ \pmod {2^{5}-1}}\\&\equiv {110000}_{2}{\pmod {2^{5}-1}}\\&\equiv {10000}_{2}+ 1_{2}{\pmod {2^{5}-1}}\\&\equiv {10001}_{2}{\pmod {2^{5}-1}}\\&={10001}_ {2}\\&=17\end{aligned}}

Při použití této modulo metody bude výpočetní složitost testu určena složitostí kvadratického algoritmu. Délka je bit a algoritmus pro násobení dvou čísel, například "ve sloupci", je složitý [4] . Protože kvadratura nastane jednou v testu, výpočetní složitost algoritmu je [14] . Test lze urychlit použitím rychlých násobicích algoritmů pro velká celá čísla, jako je Schönhage-Strassenova metoda násobení . Složitost testu v tomto případě bude . $M_{p}$ $p$ $O(p^{2})$ $O(p)$ $O(p^{3})$ $O(p^{2}\ln {p}\ln {\ln {p)))$

Variace a zobecnění

Podmínka v testu může být oslabena [8] a vyžaduje pouze to , z čehož bezprostředně vyplývá: ${\displaystyle S_{p-2}\equiv \pm 2^{\frac {p+1}{2)){\pmod {M_{p))))$

{\displaystyle S_{p-1}=2^{p+1}-2=2(2^{p}-1)\equiv 0{\pmod {M_{p))))

V roce 1930 Lemaire odvodil kritérium primality pro čísla ve tvaru , kde , a v roce 1969 Hans Riesel upravil Lucas-Lehmerův test pro čísla tohoto tvaru, který později doplnil Stechkin [9] . Test je možné zobecnit na čísla tvaru [15] . $k2^{n}-1$ ${\displaystyle k<2^{n))$ $A2^{{2n}}+B2^{{n}}-1$

Williams dokázal kritéria primality podobná Luc-Lehmerovu testu pro čísla ve tvarua, stejně jako pro některá čísla ve tvaru, kde je prvočíslo [9] . $k3^{n}-1\;(k<3^{n})$ $k2^{n}3^{m}-1,\;(k<2^{n}3^{m})$ $kq^{n}-1$ $q>3$ $(k<q^{n})$

Existuje obecnější test primality , který je použitelný pro jakékoli přirozené číslo , pokud je známa úplná nebo částečná rozklad čísla nebo [4] . $N$ $N-1$ $N+1$

Aplikace

Díky Lucas-Lehmerově testu drží Mersennova prvočísla prvenství jako největší známá prvočísla , i když ještě před existencí testu byla Mersennova čísla téměř vždy největšími prvočísly. Takže v roce 1588 byla prokázána jednoduchost čísel a [16] . $M_{17}$ $M_{19}$

Euclid dokázal, že jakékoli číslo tvaru je dokonalé , pokud je prvočíslo, a Euler ukázal, že všechna sudá dokonalá čísla mají tento tvar [17] ; takže Luc-Lehmerův test vám vlastně umožňuje najít všechna sudá dokonalá čísla. ${\displaystyle 2^{p-1}(2^{p}-1)=2^{p-1}M_{p))$ $M_{p}$

Právě tento test je základem projektu distribuovaných výpočtů GIMPS , který hledá nová Mersennova prvočísla [18] , i když zatím nebylo prokázáno, že jich je nekonečně mnoho [19] .

Tento test se také používá k testování hardwaru . Například v roce 1992 AEA Technology testovala nový superpočítač od Cray pomocí programu napsaného Slowinskim k nalezení Mersennova prvočísel. Výsledkem bylo, že za 19 hodin provozu programu bylo objeveno prvočíslo [20] . $M_{756839}$

Poznámky

↑ 1 2 Jaroma J. H. Poznámka k Lucas–Lehmerově testu // Irish Math . soc. Bulletin - Irish Mathematical Society , 2004. - Vol. 54. - S. 63-72. — ISSN 0791-5578
↑ OEIS sekvence A003010 _
↑ Abhijit Das. Výpočetní teorie čísel. - 2. vyd. - CRC Press, 2016. - S. 290-292. — 614 s. - (Diskrétní matematika a její aplikace). — ISBN 1482205823 .
↑ 1 2 3 4 Crandall R., Pomerance K. Prvočísla . Kryptografické a výpočetní aspekty = Prvočísla: A Computational Perspective / per. z angličtiny. A. V. Begunts, Ya, V. Wegner, V. V. Knotko, S. N. Preobraženskij, I. S. Sergeev. - M . : URSS, Dům knihy "Librokom", 2011. - S. 198-216, 498-500, 510-513. — 664 s. - ISBN 978-5-453-00016-6 , 978-5-397-02060-2.
↑ Robinson R. M. Mersenne a Fermatova čísla // Proc . amer. Matematika. soc. / K. Ono - AMS , 1954. - Sv. 5, Iss. 5. - S. 842. - ISSN 0002-9939 ; 1088-6826 – doi:10.2307/2031878
↑ Kravitz S. The Lucas–Lehmer Test for Mersenne Numbers (anglicky) // Fibonacci Quarterly / C. Cooper - The Fibonacci Association , 1970. - Vol. 8, Iss. 1. - S. 1-3. — ISSN 0015-0517 ; 2641-340X
↑ OEIS sekvence A018844 _
↑ 1 2 Trost E. Prvočísla = Primzahlen / ed. A. O. Gelfond, přel. s ním. N. I. Feldman. - M. : Fizmatlit, 1959. - S. 42-46. — 137 s. — 15 000 výtisků.
↑ 1 2 3 4 5 Williams H. Testování prvočísel pomocí počítačů = Testování primality na počítači // Lupanov O. B. Cybernetic collection: journal / transl. z angličtiny. S. V. Chudová. - M .: Mir, 1986. - Vydání. 23 . - S. 51-99 . — ISBN N/A, LBC 32,81, MDT 519,95 .
↑ Ribenboim P. The Little Book of Bigger Primes (anglicky) - 2. vydání - Springer-Verlag New York , 2004. - S. 75-87. — 356 s. — ISBN 978-0-387-21820-5
↑ Devlin K. Mathematics (anglicky) : The New Golden Age - 2. vydání - UK : Penguin Books , 1998. - S. 75-87. — 320p. — ISBN 978-0-14-193605-5
↑ 1 2 Koshy T. Elementární teorie čísel s aplikacemi. — 2. vydání. - Academic Press, 2007. - S. 369-381. — 800p. — ISBN 9780080547091 .
↑ Bach E., Shallit J. Algorithmic Number Theory, sv. 1: Efektivní algoritmy. - The MIT Press, 1996. - S. 41-66. — 496 s. — (Základy výpočetní techniky). — ISBN 978-0262024051 .
↑ Williams H. C. A Class of Primality Tests for Trinomials which include the Lucas-Lehmer Test // Pacific Journal of Mathematics - Mathematical Sciences Publishers , 1982. - Vol. 98, Iss. 2. - S. 477-494. — ISSN 0030-8730 ; 1945-5844 – doi:10.2140/PJM.1982.98.477
↑ Rosen K. H. Elementary Number Theory and its Applications (Angl.) - 5 - Addison-Wesley , 2004. - S. 261-265. — 744 s. — ISBN 978-0-321-23707-1
↑ Hasse G. Přednášky o teorii čísel = Vorlesungen über die Theorie der algebraischen Zahlen / ed. I. R. Shafarevich, přel. s ním. V. B. Demjanová. - M . : Nakladatelství zahraniční literatury, 1953. - S. 36-44. — 528 s.
↑ Strategie matematiky a výzkumu . GIMPS . Získáno 4. prosince 2016. Archivováno z originálu dne 20. listopadu 2016.
↑ Wolf M. Computer Experiments with Mersenne Primes // Computational Methods in Science and Technology - 2013. - Vol . 19, Iss. 3. - S. 157-165. — ISSN 1505-0602 ; 2353-9453 – doi:10.12921/CMST.2013.19.03.157-165 – arXiv:1112.2412
↑ Clawson C. C. Mathematical Mysteries (anglicky) : The Beauty and Magic of Numbers - Springer US , 1996. - S. 174. - 314 s. - ISBN 978-0-306-45404-2 - doi:10.1007/978-1-4899-6080-1

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin