Luc-Lehmer test

Lucas -Lehmer-testet ( eng. Lucas-Lehmer-testet , förkortat LLT ) är ett polynomiskt , deterministiskt och ovillkorligt (det vill säga inte beroende av obevisade hypoteser) primalitetstest för Mersenne-tal . Formulerad av Édouard Lucas 1878 och bevisad av Lemaire 1930 [ ⇨ .

Givet ett primtal tillåter testet polynomtid för bitlängden för Mersennetalet för att avgöra om det är primtal eller sammansatt . Beviset för testets giltighet förlitar sig starkt på Lucas-funktionerna , som gjorde det möjligt att generalisera Lucas-Lehmer-testet till några tal vars form skiljer sig från Mersenne-talen . $p>2$ $sid$ $M_{p}=2^{p}-1$ $M_{p}$

Tack vare detta test har de största kända primtalen nästan alltid varit Mersenne-primtal, även innan datorernas tillkomst ; det är han som ligger till grund för GIMPS distributed computing- projektet , som är engagerad i sökandet efter nya Mersenne-primtal. Det är också intressant för dess samband med jämna perfekta tal .

Formulering

Testet är baserat på följande kriterier för enkelheten hos Mersenne-tal [1] :

Låt vara ett enkelt udda tal. Ett Mersennetal är primtal om och endast om det delar den :e termen i sekvensen $sid$ $M_{p}=2^{p}-1$ $(p-1)$

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

[2] ,

ges rekursivt : $S_{k}={\begin{cases}4&k=1,\\S_{k-1}^{2}-2&k>1.\end{cases))$

Lemaire , 1930

För att kontrollera enkelheten beräknas talföljden modulo numret (det vill säga, inte talen i sig beräknas , vars längd växer exponentiellt , men resten efter division med , vars längd begränsas av bitar ). Det sista numret i denna sekvens kallas Lucas-Lehmer-resten [3] . Således är ett Mersenne-tal primtal om och endast om talet är ett udda primtal och Lucas-Lehmer-resten är noll. Algoritmen i sig kan skrivas som pseudokod [4] : $M_{p}$ ${\displaystyle S_{1},S_{2},\ldots ,S_{p-1))$ $M_{p}$ $S_k$ $S_k$ $M_{p}$ $sid$ $S_{p-1}{\bmod {M}}_{p}$ $M_{p}$ $sid$

LLT (p) ►Inmatning: udda primtal sid S=4 k = 1 M = 2 p − 1 Till k != p - 1 S = ((S × S) − 2) mod M k += 1 End of loop Om S = 0 exekvera Return SIMPLE annars Return COMPOUND Slutvillkor

Värdena för vilka primalitetskriteriet är giltigt bildar en sekvens: [5] [6] [7] . $S_{1}$ $4,\;10,\;52,\;724,\;970,\;10084,\;\ldots$

Det är inte nödvändigt att kontrollera alla udda primtal i direkt uppräkning, eftersom vissa Mersenne-tal av en speciell form alltid är sammansatta, vilket till exempel följer av följande teorem som bevisats av Euler [ 8] : $sid$

Om tal och är primtal, då . $p=4n+3$ $q=2p+1=8n+7$ $M_{p}\equiv 0{\pmod {q))$

Bevis

Ett tillvägagångssätt för beviset är baserat på användningen av Lukas funktioner :

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

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

var finns rötterna till andragradsekvationen $\alpha ,\;\beta$

x^{2}-Px+Q=0

med en diskriminant , och och är coprime . $D=P^{2}-4Q,$ $P$ $F$

I synnerhet används vissa egenskaper hos dessa funktioner i beviset, nämligen [9] :

ett.

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}}\ höger)^{n}

4. Om , , och

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

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

(Q,N)=1

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

, sedan

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

5. Om är prime, så att samprima med , dividerar sedan med ,

sid

2DQ

sid

sid

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

där och är Legendre-symbolen .

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

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

Bevisschema [9] :

Nödvändighet

Från egenskap 4. modulo för , , följer det: $N=M_{p}$ $P=2$ $Q=-2$

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

och av fastighet 2.

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

det är därför

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

och

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$ , så om är prime, så delar den sig också från de två sista egenskaperna $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)

Vidare från fastigheterna 1. och 2.

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

men av fastighet 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}}

det vill säga delar , och därmed . $N$ $V_{\frac {N+1}{2}}(2,-2)$ $S_{p-1}$

Tillräcklighet

Om den delar sig så följer det av beviset på nödvändigheten att den delar och . samprima med av egenskap 1., och efter egenskap 2. - delar . Men då kan varje primtalsdelare av talet representeras som , det vill säga primtal. $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}$

Historik

Kriteriet på enkelhet föreslogs av den franske matematikern Lucas 1878 . Lucas visade i synnerhet att algoritmen tillåter primalitetstestning för primtal [9] . År 1930 bevisade den amerikanske matematikern Lehmer till fullo giltigheten av kriteriet för alla udda primtal i sin avhandling för doktorsexamen i filosofi [1] . $M_{p}$ $p\equiv 1{\pmod {4}}$ $sid$

År 1952, med stöd av Lemaire, utförde Robinson beräkningar på SWAC -datorn med hjälp av Luc-Lehmer-testet, vilket resulterade i upptäckten av primtal och . Senare samma år upptäcktes , och [10] . $M_{{521}}$ $M_{{607}}$ $M_{{1279}}$ $M_{{2203}}$ $M_{{2281}}$

Den enkla implementeringen av testet och tillväxten av datorkraften hos datorer gjorde det möjligt för praktiskt taget vem som helst att söka efter Mersenne-primtal. Så 1978 bevisade två amerikanska gymnasieelever Laura Nickel och Kurt Knoll (Lemaire lärde dem sifferteori) enkelheten i siffror i tre års arbete med CDC Cyber 176 superdator vid University of California [11] . $M_{21701}$

Den största kända Mersenne-primen för 2018, erhållen med Lucas-Lehmer-testet, är . $M_{82589933}$

Exempel

Kravet på uddahet i kriteriets tillstånd är väsentligt, eftersom det är enkelt , men . $sid$ $M_{2}=2^{2}-1=3$ $S_{1}\equiv 4{\pmod {3}}=1\not =0$

Talet är primtal [13] . Verkligen, $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

Att tillämpa testet på ett nummer visar att det är sammansatt [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

Verkligen ,. $2047=23\cdot 89$

Beräkningskomplexitet

Det finns två huvudoperationer i testet som övervägs: kvadrering och modulodelning . En effektiv algoritm för modulo ett Mersenne-tal på en dator (faktiskt reducerad till några bitskiftsoperationer ) ges av följande teorem [4] :

För ett heltal och ett Mersenne -tal sker modulokongruens $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}}}

dessutom är multiplikation med modulo ekvivalent med en vänstercyklisk förskjutning med en bit (om , så utförs förskjutningen i motsatt riktning). $2^k$ $M_{p}$ $k$ $k<0$

Till exempel, för att beräkna resten av att dividera ett tal med , måste du konvertera det ursprungliga talet till binär form: , och, enligt satsen, dela upp i två delar varje gång det överskrider : $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}}}\right\rfloor {\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}}

När du använder denna modulo-metod kommer testets beräkningskomplexitet att bestämmas av kvadreringsalgoritmens komplexitet. Längden är lite, och algoritmen för att multiplicera två tal, till exempel "i en kolumn", har komplexitet [4] . Eftersom kvadrering sker en gång i testet är algoritmens beräkningskomplexitet [14] . Testet kan påskyndas genom att använda snabba multiplikationsalgoritmer för stora heltal, som multiplikationsmetoden Schönhage-Strassen . Testets komplexitet i detta fall kommer att vara . $M_{p}$ $sid$ $O(p^{2})$ $O(p)$ $O(p^{3})$ $O(p^{2}\ln {p}\ln {\ln {p)))$

Variationer och generaliseringar

Tillståndet i testet kan försvagas [8] och kräver endast det , vilket omedelbart innebär: ${\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))))

År 1930 härledde Lemaire ett primatitetskriterium för siffror av formen , där , och 1969 modifierade Hans Riesel Lucas-Lehmer-testet för nummer av denna form, som senare kompletterades av Stechkin [9] . Det är möjligt att generalisera testet till siffror av formen [15] . $k2^{n}-1$ ${\displaystyle k<2^{n))$ $A2^{{2n}}+B2^{{n}}-1$

Williams bevisade primalitetskriterier som liknar Luc-Lehmer-testet för siffror av formenoch, såväl som för vissa nummer av formen, där är ett primtal [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})$

Det finns ett mer allmänt primatitetstest , som är tillämpligt för alla naturliga tal , om den fullständiga eller partiella faktoriseringen av numret eller [4] är känd . $N$ $N-1$ $N+1$

Applikationer

Tack vare Lucas-Lehmer-testet har Mersenne-primtal ledningen som de största kända primtalen , även om Mersenne-talen nästan alltid var de största primtalen redan innan testet existerade. Så, 1588, enkelheten av siffrorna och bevisades [16] . $M_{17}$ $M_{19}$

Euklid bevisade att vilket tal som helst i formen är perfekt om är primtal, och Euler visade att alla jämna perfekta tal har denna form [17] ; så Luc-Lehmer-testet låter dig faktiskt hitta alla jämna perfekta siffror. ${\displaystyle 2^{p-1}(2^{p}-1)=2^{p-1}M_{p))$ $M_{p}$

Det är detta test som ligger till grund för GIMPS distribuerade datorprojekt , som letar efter nya Mersenne-primtal [18] , även om det ännu inte har bevisats att det finns oändligt många av dem [19] .

Detta test används också för att testa hårdvara . Till exempel, 1992, testade AEA Technology en ny superdator från Cray med hjälp av ett program skrivet av Slowinski för att hitta Mersenne-primtal. Som ett resultat upptäcktes ett primtal under 19 timmars programdrift [20] . $M_{756839}$

Anteckningar

↑ 1 2 Jaroma J. H. Note on the Lucas–Lehmer Test // Irish Math . soc. Bulletin - Irish Mathematical Society , 2004. - Vol. 54. - S. 63-72. — ISSN 0791-5578
↑ OEIS - sekvens A003010 _
↑ Abhijit Das. Beräkningstalteori. - 2:a uppl. - CRC Press, 2016. - S. 290-292. — 614 sid. - (Diskret matematik och dess tillämpningar). — ISBN 1482205823 .
↑ 1 2 3 4 Crandall R., Pomerance K. Primtal. Kryptografiska och beräkningsaspekter = Prime Numbers: A Computational Perspective / per. från engelska. A. V. Begunts, Ya. V. Wegner, V. V. Knotko, S. N. Preobrazhensky, I. S. Sergeev. - M . : URSS, Bokhuset "Librokom", 2011. - S. 198-216, 498-500, 510-513. — 664 sid. - ISBN 978-5-453-00016-6 , 978-5-397-02060-2.
↑ Robinson R. M. Mersenne och Fermat Numbers // Proc . amer. Matematik. soc. / K. Ono - AMS , 1954. - Vol. 5, Iss. 5. - P. 842. - ISSN 0002-9939 ; 1088-6826 - doi:10.2307/2031878
↑ Kravitz S. Lucas–Lehmer-testet för Mersenne Numbers (Eng.) // Fibonacci Quarterly / C. Cooper - Fibonacci Association , 1970. - Vol. 8, Iss. 1. - S. 1-3. — ISSN 0015-0517 ; 2641-340X
↑ OEIS - sekvens A018844 _
↑ 1 2 Trost E. Primtal = Primzahlen / ed. A. O. Gelfond, övers. med honom. N. I. Feldman. - M. : Fizmatlit, 1959. - S. 42-46. — 137 sid. — 15 000 exemplar.
↑ 1 2 3 4 5 Williams H. Testa siffror för primat med hjälp av datorer = Primalitetstestning på en dator // Lupanov O. B. Cybernetisk samling: journal / transl. från engelska. S.V. Chudova. - M . : Mir, 1986. - Utgåva. 23 . - S. 51-99 . — ISBN N/A, LBC 32.81, UDC 519.95 .
↑ Ribenboim P. The Little Book of Bigger Primes (engelska) - 2:a upplagan - Springer-Verlag New York , 2004. - P. 75-87. — 356 sid. — ISBN 978-0-387-21820-5
↑ Devlin K. Mathematics (engelska) : The New Golden Age - 2nd edition - UK : Penguin Books , 1998. - P. 75-87. — 320p. — ISBN 978-0-14-193605-5
↑ 1 2 Koshy T. Elementär nummerteori med tillämpningar. — 2:a upplagan. - Academic Press, 2007. - S. 369-381. — 800p. — ISBN 9780080547091 .
↑ Bach E., Shallit J. Algorithmic Number Theory, Vol. 1: Effektiva algoritmer. - The MIT Press, 1996. - S. 41-66. — 496 sid. — (Fundament of Computing). — ISBN 978-0262024051 .
↑ Williams H. C. A Class of Primity Tests for Trinomials which include the Lucas-Lehmer Test // Pacific Journal of Mathematics - Mathematical Sciences Publishers , 1982. - Vol. 98, Iss. 2. - P. 477-494. — ISSN 0030-8730 ; 1945-5844 - doi:10.2140/PJM.1982.98.477
↑ Rosen K. H. Elementär talteori och dess tillämpningar (eng.) - 5 - Addison-Wesley , 2004. - P. 261-265. — 744 sid. — ISBN 978-0-321-23707-1
↑ Hasse G. Föreläsningar om talteori = Vorlesungen über die Theorie der algebraischen Zahlen / ed. I. R. Shafarevich, övers. med honom. V. B. Demyanova. - M . : Förlag för utländsk litteratur, 1953. - S. 36-44. — 528 sid.
↑ Matematik och forskningsstrategi . GIMPS . Hämtad 4 december 2016. Arkiverad från originalet 20 november 2016.
↑ Wolf M. Datorexperiment med 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 (engelska) : The Beauty and Magic of Numbers - Springer US , 1996. - P. 174. - 314 sid. - ISBN 978-0-306-45404-2 - doi:10.1007/978-1-4899-6080-1

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm