Testul Luc-Lehmer

Testul Lucas-Lehmer ( ing. testul Lucas-Lehmer , abreviat LLT ) este un test de primalitate polinom , determinist și necondiționat (adică nu depinde de ipoteze nedemonstrate) pentru numerele Mersenne . Formulat de Édouard Lucas în 1878 și dovedit de Lemaire în 1930 .

Având în vedere un număr prim , testul permite timpul polinomial al lungimii de biți a numărului Mersenne pentru a determina dacă este prim sau compus . Dovada validității testului se bazează în mare măsură pe funcțiile Lucas , care au făcut posibilă generalizarea testului Lucas-Lehmer la unele numere a căror formă este diferită de numerele Mersenne . $p>2$ $p$ $M_{p}=2^{p}-1$ $M_{p}$

Datorită acestui test, cele mai mari numere prime cunoscute au fost aproape întotdeauna numere prime Mersenne, chiar înainte de apariția computerelor ; el este cel care stă la baza proiectului de calcul distribuit GIMPS , care este angajat în căutarea de noi numere prime Mersenne. Este interesant și pentru legătura cu numerele pare perfecte .

Formulare

Testul se bazează pe următoarele criterii pentru simplitatea numerelor Mersenne [1] :

Să fie un simplu număr impar. Un număr Mersenne este prim dacă și numai dacă împarte al treilea termen al șirului $p$ $M_{p}=2^{p}-1$ $(p-1)$

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

[2] ,

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

Lemaire , 1930

Pentru a verifica simplitatea , succesiunea de numere este calculată modulo numărul (adică nu se calculează numerele în sine , a căror lungime crește exponențial , ci resturile după împărțirea la , a căror lungime este limitată de biți ). Ultimul număr din această secvență se numește restul Lucas-Lehmer [3] . Astfel, un număr Mersenne este prim dacă și numai dacă numărul este un prim impar și restul Lucas-Lehmer este zero. Algoritmul în sine poate fi scris ca pseudocod [4] : $M_{p}$ $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) ►Introducere: număr prim impar p S=4 k = 1 M = 2 p − 1 Până la k != p - 1 S = ((S × S) − 2) mod M k += 1 Sfârșitul buclei Dacă S = 0 executați Return SIMPLE altfel Returnați COMPOUND Condiția de sfârșit

Valorile pentru care criteriul de primalitate este valabil formează o secvență: [5] [6] [7] . $S_{1}$ $4,\;10,\;52,\;724,\;970,\;10084,\;\ldots$

Nu este necesar să se verifice toate numerele prime impare în enumerarea directă, deoarece unele numere Mersenne de o formă specială sunt întotdeauna compuse, ceea ce decurge, de exemplu, din următoarea teoremă demonstrată de Euler [ 8] : $p$

Dacă numerele și sunt prime, atunci . $p=4n+3$ $q=2p+1=8n+7$ $M_{p}\equiv 0{\pmod {q)}$

Dovada

O abordare a dovezii se bazează pe utilizarea funcțiilor lui Luke :

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

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

unde sunt rădăcinile ecuației pătratice $\alpha ,\;\beta$

x^{2}-Px+Q=0

cu un discriminant și și sunt coprime . $D=P^{2}-4Q,$ $P$ $Q$

În special, unele proprietăți ale acestor funcții sunt utilizate în demonstrație, și anume [9] :

unu.

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}}=\left({\frac {P+{\sqrt {D}}}{2}}\ dreapta)^{n}

4. Dacă , , și

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

Q'\equiv Q{\pmod {N}}

(Q,N)=1

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

, apoi

{\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. Dacă este prim, astfel încât coprim cu , atunci se împarte la ,

p

2DQ

p

p

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

unde , și este simbolul Legendre .

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

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

Schema de probă [9] :

Necesitate

Din proprietatea 4. modulo pentru , , rezultă: $N=M_{p}$ $P=2$ $Q=-2$

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

și după proprietatea 2.

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

de aceea

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

și

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$ , deci dacă este prim, atunci se împarte și de ultimele două proprietăți $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)

În plus, din proprietățile 1. și 2.

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

dar prin proprietatea 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}}

adică împarte , și deci . $N$ $V_{\frac {N+1}{2}}(2,-2)$ $S_{p-1}$

Suficiență

Dacă se împarte , atunci din dovada necesităţii rezultă că împarte şi . coprim cu prin proprietatea 1., iar prin proprietatea 2. - împarte . Dar atunci fiecare divizor prim al numărului poate fi reprezentat ca , adică , prim. $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}$

Istorie

Criteriul simplității a fost propus de matematicianul francez Lucas în 1878 . În special, Lucas a arătat că algoritmul permite testarea primalității pentru numere prime [9] . În 1930, matematicianul american Lehmer a dovedit pe deplin validitatea criteriului pentru toate numerele prime impare în disertația sa pentru gradul de doctor în filozofie [1] . $M_{p}$ $p\equiv 1{\pmod {4}}$ $p$

În 1952, cu sprijinul lui Lemaire, Robinson a efectuat calcule pe computerul SWAC folosind testul Luc-Lehmer, care a dus la descoperirea numerelor prime și . Mai târziu, în același an, au fost descoperite și [10] . $M_{{521}}$ $M_{{607}}$ $M_{{1279}}$ $M_{{2203}}$ $M_{{2281}}$

Ușurința de implementare a testului și creșterea puterii de calcul a computerelor au permis practic oricui să caute numere prime Mersenne. Așadar, în 1978, doi liceeni americani Laura Nickel și Kurt Knoll (Lemaire i-a predat teoria numerelor) au dovedit simplitatea numărului în 3 ani de muncă folosind supercomputerul CDC Cyber 176 de la Universitatea din California [11] . $M_{21701}$

Cel mai mare prim Mersenne cunoscut pentru 2018, obținut cu ajutorul testului Lucas-Lehmer, este . $M_{82589933}$

Exemple

Cerința de ciudat în condiția criteriului este esențială, deoarece este simplă , dar . $p$ $M_{2}=2^{2}-1=3$ $S_{1}\equiv 4{\pmod {3}}=1\not =0$

Numărul este prim [13] . Într-adevăr, $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

Aplicarea testului unui număr arată că acesta este compus [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

Într-adevăr, . $2047=23\cdot 89$

Complexitate computațională

Există două operații principale în testul luat în considerare: pătratul și împărțirea modulo . Un algoritm eficient pentru modulo un număr Mersenne pe un computer (reducându-se de fapt la câteva operații de deplasare de biți ) este dat de următoarea teoremă [4] :

Pentru un întreg și un număr Mersenne , are loc congruența modulo $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}}}

în plus, înmulțirea cu modulo este echivalentă cu o deplasare ciclică la stânga cu un bit (dacă , atunci deplasarea este efectuată în direcția opusă). $2^k$ $M_{p}$ $k$ $k<0$

De exemplu, pentru a calcula restul împărțirii unui număr la , trebuie să convertiți numărul original în formă binară: și, conform teoremei, împărțiți în două părți de fiecare dată când depășește : $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{aliniat}}

Când se utilizează această metodă modulo, complexitatea de calcul a testului va fi determinată de complexitatea algoritmului de pătrare. Lungimea este puțin, iar algoritmul de înmulțire a două numere, de exemplu, „într-o coloană”, are complexitate [4] . Deoarece pătratul are loc o dată în test, complexitatea de calcul a algoritmului este [14] . Testul poate fi accelerat prin utilizarea algoritmilor de multiplicare rapidă pentru numere întregi mari, cum ar fi metoda de înmulțire Schönhage-Strassen . Complexitatea testului în acest caz va fi de . $M_{p}$ $p$ $O(p^{2})$ $O(p)$ $O(p^{3})$ $O(p^{2}\ln {p}\ln {\ln {p)})$

Variații și generalizări

Condiția din test poate fi slăbită [8] și necesită doar aceea , ceea ce implică imediat: $S_{p-2}\equiv \pm 2^{\frac {p+1}{2}}{\pmod {M_{p}}}$

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

În 1930, Lemaire a derivat un criteriu de primalitate pentru numerele de forma , unde , iar în 1969 Hans Riesel a modificat testul Lucas-Lehmer pentru numerele de această formă, care a fost completat ulterior de Stechkin [9] . Este posibil să se generalizeze testul la numere de forma [15] . $k2^{n}-1$ $k<2^{n)$ $A2^{{2n}}+B2^{{n}}-1$

Williams a demonstrat criterii de primalitate similare testului Luc-Lehmer pentru numere de formași, precum și pentru unele numere de forma, unde este prim [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})$

Există un test de primalitate mai general , care este aplicabil pentru orice număr natural , dacă se cunoaște factorizarea totală sau parțială a numărului sau [4] . $N$ $N-1$ $N+1$

Aplicații

Datorită testului Lucas-Lehmer, numerele prime Mersenne dețin liderul ca fiind cele mai mari numere prime cunoscute , deși chiar înainte de existența testului, numerele Mersenne erau aproape întotdeauna cele mai mari numere prime. Deci, în 1588, simplitatea numerelor și a fost dovedită [16] . $M_{17}$ $M_{19}$

Euclid a demonstrat că orice număr de formă este perfect dacă este prim, iar Euler a arătat că toate numerele perfecte par au această formă [17] ; astfel încât testul Luc-Lehmer vă permite de fapt să găsiți toate numerele pare perfecte. $2^{p-1}(2^{p}-1)=2^{p-1}M_{p)$ $M_{p}$

Acesta este testul care stă la baza proiectului de calcul distribuit GIMPS , care caută noi numere prime Mersenne [18] , deși nu s-a dovedit încă că există o infinitate de ele [19] .

Acest test este folosit și pentru a testa hardware -ul . De exemplu, în 1992, AEA Technology a testat un nou supercomputer de la Cray folosind un program scris de Slowinski pentru a găsi numerele prime Mersenne. Ca rezultat, un număr prim a fost descoperit în 19 ore de funcționare a programului [20] . $M_{756839}$

Note

↑ 1 2 Jaroma J. H. Notă despre testul Lucas–Lehmer // Irish Math . soc. Buletin - Societatea Irlandeză de Matematică , 2004. - Vol. 54. - P. 63-72. — ISSN 0791-5578
↑ Secvența OEIS A003010 _
↑ Abhijit Das. Teoria numerelor computaționale. - Ed. a II-a. - CRC Press, 2016. - P. 290-292. — 614 p. - (Matematică discretă și aplicațiile sale). — ISBN 1482205823 .
↑ 1 2 3 4 Crandall R., Pomerance K. Numerele prime. Aspecte criptografice și de calcul = Prime Numbers: A Computational Perspective / per. din engleza. A. V. Begunts, Ya. V. Wegner, V. V. Knotko, S. N. Preobrazhensky, I. S. Sergeev. - M . : URSS, Casa de carte „Librokom”, 2011. - S. 198-216, 498-500, 510-513. — 664 p. - ISBN 978-5-453-00016-6 , 978-5-397-02060-2.
↑ Robinson R. M. Mersenne și numerele Fermat // Proc . amer. Matematică. soc. / K. Ono - AMS , 1954. - Vol. 5, Iss. 5. - P. 842. - ISSN 0002-9939 ; 1088-6826 - doi:10.2307/2031878
↑ Kravitz S. Testul Lucas–Lehmer pentru numerele Mersenne (ing.) // Fibonacci Quarterly / C. Cooper - The Fibonacci Association , 1970. - Vol. 8, Iss. 1. - P. 1-3. — ISSN 0015-0517 ; 2641-340X
↑ Secvența OEIS A018844 _
↑ 1 2 Trost E. Numere prime = Primzahlen / ed. A. O. Gelfond, trad. cu el. N. I. Feldman. - M. : Fizmatlit, 1959. - S. 42-46. — 137 p. — 15.000 de exemplare.
↑ 1 2 3 4 5 Williams H. Testarea numerelor pentru primalitate cu ajutorul computerelor = Primality testing on a computer // Lupanov O. B. Cybernetic collection: journal / trad. din engleza. S. V. Chudova. - M . : Mir, 1986. - Numărul. 23 . - S. 51-99 . — ISBN N/A, LBC 32.81, UDC 519.95 .
↑ Ribenboim P. The Little Book of Bigger Primes (engleză) - ediția a 2-a - Springer-Verlag New York , 2004. - P. 75-87. — 356 p. — ISBN 978-0-387-21820-5
↑ Devlin K. Mathematics (engleză) : The New Golden Age - Ediția a 2-a - Marea Britanie : Penguin Books , 1998. - P. 75-87. — 320p. — ISBN 978-0-14-193605-5
↑ 1 2 Koshy T. Teoria elementară a numerelor cu aplicații. — ediția a II-a. - Presa Academică, 2007. - P. 369-381. — 800p. — ISBN 9780080547091 .
↑ Bach E., Shallit J. Teoria numerelor algoritmice, voi. 1: Algoritmi eficienți. - The MIT Press, 1996. - P. 41-66. — 496 p. — (Fundații ale calculului). — ISBN 978-0262024051 .
↑ Williams H. C. A Class of Primality Tests for Trinomials Which Includes 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. Teoria elementară a numerelor și aplicațiile sale (ing.) - 5 - Addison-Wesley , 2004. - P. 261-265. — 744 p. — ISBN 978-0-321-23707-1
↑ Hasse G. Prelegeri de teoria numerelor = Vorlesungen über die Theorie der algebraischen Zahlen / ed. I. R. Şafarevici, trad. cu el. V. B. Demyanova. - M . : Editura de literatură străină, 1953. - S. 36-44. — 528 p.
↑ Matematică și strategie de cercetare . GIMPS . Preluat la 4 decembrie 2016. Arhivat din original la 20 noiembrie 2016.
↑ Wolf M. Computer Experiments with Mersenne Primes // Computational Methods in Science and Technology - 2013. - Vol . 19, Iss. 3. - P. 157-165. — ISSN 1505-0602 ; 2353-9453 - doi:10.12921/CMST.2013.19.03.157-165 - arXiv:1112.2412
↑ Clawson C. C. Mathematical Mysteries (engleză) : The Beauty and Magic of Numbers - Springer US , 1996. - P. 174. - 314 p. - ISBN 978-0-306-45404-2 - doi:10.1007/978-1-4899-6080-1

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin