Luc-Lehmer test

Lucas - Lehmer-testen ( eng. Lucas-Lehmer-testen , forkortelse LLT ) er en polynomisk , deterministisk og ubetinget (det vil sige ikke afhængig af ubeviste hypoteser) primalitetstest for Mersenne-tal . Formuleret af Édouard Lucas i 1878 og bevist af Lemaire i 1930 .

Givet et primtal tillader testen polynomisk tid af bitlængden af Mersenne-tallet for at bestemme, om det er primtal eller sammensat . Beviset for testens gyldighed bygger i høj grad på Lucas-funktionerne , som gjorde det muligt at generalisere Lucas-Lehmer-testen til nogle tal, hvis form er forskellig fra Mersenne-tallene . $p>2$ $s$ $M_{p}=2^{p}-1$ $M_{p}$

Takket være denne test har de største kendte primtal næsten altid været Mersenne-primtal, selv før computernes fremkomst ; det er ham, der ligger til grund for GIMPS distributed computing- projektet , som er engageret i jagten på nye Mersenne-primtal. Det er også interessant for dets forbindelse med lige perfekte tal .

Ordlyd

Testen er baseret på følgende kriterier for enkelheden af Mersenne-tallene [1] :

Lad være et simpelt ulige tal. Et Mersenne-tal er primtal, hvis og kun hvis det deler sekvensens th led $s$ $M_{p}=2^{p}-1$ $(s-1)$

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

[2] ,

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

Lemaire , 1930

For at kontrollere enkelheden beregnes talrækken modulo antallet (det vil sige, at ikke tallene i sig selv beregnes , hvis længde vokser eksponentielt , men resten efter at dividere med , hvis længde er begrænset af bits ). Det sidste tal i denne sekvens kaldes Lucas-Lehmer-resten [3] . Et Mersenne-tal er således primtal, hvis og kun hvis tallet er et ulige primtal, og Lucas-Lehmer-resten er nul. Selve algoritmen kan skrives som pseudokode [4] : $M_{p}$ ${\displaystyle S_{1},S_{2},\ldots ,S_{p-1))$ $M_{p}$ $S_k$ $S_k$ $M_{p}$ $s$ $S_{p-1}{\bmod {M}}_{p}$ $M_{p}$ $s$

LLT (p) ►Indtast: ulige primtal s S=4 k = 1 M = 2 p − 1 Indtil k != p - 1 S = ((S × S) − 2) mod M k += 1 End of loop Hvis S = 0 udfør Return SIMPLE ellers Return COMPOUND Slutbetingelse

De værdier , som primalitetskriteriet er gyldigt for, danner en sekvens: [5] [6] [7] . $S_{1}$ $4,\;10,\;52,\;724,\;970,\;10084,\;\ldots$

Det er ikke nødvendigt at kontrollere alle ulige primtal i direkte opregning, da nogle Mersenne-tal i en speciel form altid er sammensatte, hvilket f.eks. følger af følgende sætning bevist af Euler [ 8] : $s$

Hvis tal og er primtal, så . $p=4n+3$ $q=2p+1=8n+7$ $M_{p}\equiv 0{\pmod {q))$

Bevis

En tilgang til beviset er baseret på brugen af Lukas funktioner :

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

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

hvor er rødderne til andengradsligningen $\alpha ,\;\beta$

x^{2}-Px+Q=0

med en diskriminant , og og er coprime . $D=P^{2}-4Q,$ $P$ $Q$

Især nogle egenskaber ved disse funktioner bruges i beviset, nemlig [9] :

en.

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

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

{\frac {V_{n}+{\sqrt {D}}U_{n}}{2}}=\venstre({\frac {P+{\sqrt {D}}}{2}}\ højre)^{n}

4. Hvis , , og

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

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

(Q,N)=1

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

, derefter

{\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. Hvis er prime, sådan at coprime med , så dividerer med ,

s

2DQ

s

s

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

hvor , og er Legendre-symbolet .

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

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

Bevisskema [9] :

Nødvendighed

Fra ejendom 4. modulo for , , følger: $N=M_{p}$ $P=2$ $Q=-2$

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

og af ejendom 2.

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

derfor

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$ , så hvis er prime, så deler den sig også fra de to sidste egenskaber $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)

Yderligere fra egenskab 1. og 2.

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

men af ejendom 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 vil sige deler , og dermed . $N$ $V_{\frac {N+1}{2}}(2,-2)$ $S_{p-1}$

Tilstrækkelighed

Hvis den deler sig , så følger det af nødvendighedsbeviset , at den deler og . coprime med ved egenskab 1., og ved egenskab 2. - dividerer . Men så kan hver primtalsdivisor af tallet repræsenteres som , altså 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}$

Historie

Kriteriet om enkelhed blev foreslået af den franske matematiker Lucas i 1878 . Især Lucas viste, at algoritmen tillader primalitetstestning for primtal [9] . I 1930 beviste den amerikanske matematiker Lehmer fuldt ud gyldigheden af kriteriet for alle ulige primtal i sin afhandling for graden af Doctor of Philosophy [1] . $M_{p}$ $p\equiv 1{\pmod {4}}$ $s$

I 1952 udførte Robinson med støtte fra Lemaire beregninger på SWAC -computeren ved hjælp af Luc-Lehmer-testen, hvilket resulterede i opdagelsen af primtal og . Senere samme år blev , og [10] opdaget . $M_{{521}}$ $M_{{607}}$ $M_{{1279}}$ $M_{{2203}}$ $M_{{2281}}$

Den lette implementering af testen og væksten i computerkraften tillod praktisk talt alle at søge efter Mersenne-primtal. Så i 1978 beviste to amerikanske high school-elever Laura Nickel og Kurt Knoll (Lemaire lærte dem talteori) tallets enkelhed i 3 års arbejde ved hjælp af CDC Cyber 176 supercomputeren ved University of California [11] . $M_{21701}$

Den største kendte Mersenne prime for 2018, opnået ved hjælp af Lucas-Lehmer testen, er . $M_{82589933}$

Eksempler

Ulighedskravet i kriteriets tilstand er væsentligt, da det er enkelt , men . $s$ $M_{2}=2^{2}-1=3$ $S_{1}\equiv 4{\pmod {3}}=1\not =0$

Tallet er primtal [13] . Virkelig, $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

Anvendelse af testen på et tal viser, at det er sammensat [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

Faktisk ,. $2047=23\cdot 89$

Beregningsmæssig kompleksitet

Der er to hovedoperationer i testen under overvejelse: kvadrering og modulopdeling . En effektiv algoritme for modulo et Mersenne-tal på en computer (faktisk reduceret til et par bitskifteoperationer ) er givet ved følgende sætning [4] :

For et heltal og et Mersenne-tal finder modulo-kongruens sted $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}}}

desuden er multiplikation med modulo ækvivalent med et venstre cyklisk skift med en bit (hvis , så udføres skiftet i den modsatte retning). $2^k$ $M_{p}$ $k$ $k<0$

For at beregne resten af at dividere et tal med , skal du for eksempel konvertere det oprindelige tal til binær form: , og ifølge sætningen opdeles i to dele, hver gang det overstiger : $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\rgulv {\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}}

Ved brug af denne modulo-metode vil den beregningsmæssige kompleksitet af testen blive bestemt af kompleksiteten af kvadreringsalgoritmen. Længden er lidt, og algoritmen til at gange to tal, for eksempel "i en kolonne", har kompleksitet [4] . Da kvadrering forekommer én gang i testen, er algoritmens beregningsmæssige kompleksitet [14] . Testen kan accelereres ved at bruge hurtige multiplikationsalgoritmer for store heltal, såsom Schönhage-Strassen multiplikationsmetoden . Testens kompleksitet i dette tilfælde vil være . $M_{p}$ $s$ $O(p^{2})$ $O(p)$ $O(p^{3})$ $O(p^{2}\ln {p}\ln {\ln {p)))$

Variationer og generaliseringer

Tilstanden i testen kan svækkes [8] og kræver kun det , hvilket umiddelbart indebærer: ${\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))))

I 1930 udledte Lemaire et primalitetskriterium for tal af formen , hvor , og i 1969 ændrede Hans Riesel Lucas-Lehmer-testen for tal af denne form, som senere blev suppleret af Stechkin [9] . Det er muligt at generalisere testen til tal på formen [15] . $k2^{n}-1$ ${\displaystyle k<2^{n))$ $A2^{{2n}}+B2^{{n}}-1$

Williams beviste primalitetskriterier svarende til Luc-Lehmer-testen for tal af formenog, såvel som for nogle tal af formen, hvor er et 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})$

Der er en mere generel primatitetstest , som er anvendelig for ethvert naturligt tal , hvis den fulde eller delvise faktorisering af tallet eller [4] er kendt . $N$ $N-1$ $N+1$

Ansøgninger

Takket være Lucas-Lehmer-testen holder Mersenne-primtallene føringen som de største kendte primtal , selvom selv før testens eksistens var Mersenne-tal næsten altid de største primtal. Så i 1588 blev tallenes enkelhed bevist [16] . $M_{17}$ $M_{19}$

Euklid beviste, at et hvilket som helst tal på formen er perfekt , hvis er primtal, og Euler viste, at alle lige perfekte tal har denne form [17] ; så Luc-Lehmer-testen giver dig faktisk mulighed for at finde alle lige perfekte tal. ${\displaystyle 2^{p-1}(2^{p}-1)=2^{p-1}M_{p))$ $M_{p}$

Det er denne test, der ligger til grund for GIMPS distributed computing- projektet , som leder efter nye Mersenne-primtal [18] , selvom det endnu ikke er bevist, at der er uendeligt mange af dem [19] .

Denne test bruges også til at teste hardware . For eksempel, i 1992 testede AEA Technology en ny supercomputer fra Cray ved hjælp af et program skrevet af Slowinski for at finde Mersenne-primtal. Som et resultat blev et primtal opdaget efter 19 timers programdrift [20] . $M_{756839}$

Noter

↑ 1 2 Jaroma J. H. Notat om Lucas-Lehmer-testen // Irish Math . soc. Bulletin - Irish Mathematical Society , 2004. - Vol. 54. - S. 63-72. — ISSN 0791-5578
↑ OEIS -sekvens A003010 _
↑ Abhijit Das. Beregningsmæssig talteori. - 2. udg. - CRC Press, 2016. - S. 290-292. — 614 s. - (Diskret matematik og dens anvendelser). — ISBN 1482205823 .
↑ 1 2 3 4 Crandall R., Pomerance K. Primtal. Kryptografiske og beregningsmæssige aspekter = Primtal: A Computational Perspective / pr. fra engelsk. A. V. Begunts, Ya. V. Wegner, V. V. Knotko, S. N. Preobrazhensky, I. S. Sergeev. - M . : URSS, Boghuset "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 og 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. The Lucas–Lehmer Test for Mersenne Numbers (Eng.) // Fibonacci Quarterly / C. Cooper - The Fibonacci Association , 1970. - Vol. 8, Iss. 1. - S. 1-3. — ISSN 0015-0517 ; 2641-340X
↑ OEIS -sekvens A018844 _
↑ 1 2 Trost E. Primtal = Primzahlen / udg. A. O. Gelfond, overs. med ham. N. I. Feldman. - M. : Fizmatlit, 1959. - S. 42-46. — 137 s. — 15.000 eksemplarer.
↑ 1 2 3 4 5 Williams H. Test af numre for primalitet ved hjælp af computere = Primalitetstest på en computer // Lupanov O. B. Cybernetisk samling: journal / overs. fra engelsk. S. V. Chudova. - M . : Mir, 1986. - Udgave. 23 . - S. 51-99 . — ISBN N/A, LBC 32.81, UDC 519.95 .
↑ Ribenboim P. The Little Book of Bigger Primes (engelsk) - 2. udgave - Springer-Verlag New York , 2004. - S. 75-87. — 356 s. — ISBN 978-0-387-21820-5
↑ Devlin K. Mathematics (engelsk) : The New Golden Age - 2. udgave - UK : Penguin Books , 1998. - S. 75-87. - 320 sider. — ISBN 978-0-14-193605-5
↑ 1 2 Koshy T. Elementær talteori med anvendelser. — 2. udgave. - Academic Press, 2007. - S. 369-381. - 800p. — ISBN 9780080547091 .
↑ Bach E., Shallit J. Algorithmic Number Theory, Vol. 1: Effektive algoritmer. - The MIT Press, 1996. - S. 41-66. — 496 s. — (Foundations of Computing). — 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. Elementær talteori og dens anvendelser (eng.) - 5 - Addison-Wesley , 2004. - S. 261-265. — 744 s. — ISBN 978-0-321-23707-1
↑ Hasse G. Forelæsninger om talteori = Vorlesungen über die Theorie der algebraischen Zahlen / red. I. R. Shafarevich, oversættelse. med ham. V. B. Demyanova. - M . : Forlag for udenlandsk litteratur, 1953. - S. 36-44. — 528 s.
↑ Matematik og forskningsstrategi . GIMPS . Hentet 4. december 2016. Arkiveret fra originalen 20. november 2016.
↑ Wolf M. Computereksperimenter 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 (engelsk) : Tallenes skønhed og magi - Springer US , 1996. - S. 174. - 314 s. - ISBN 978-0-306-45404-2 - doi:10.1007/978-1-4899-6080-1

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme