{"id":2167,"date":"-0001-11-30T00:00:00","date_gmt":"-0001-11-29T23:10:04","guid":{"rendered":""},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T22:00:00","slug":"2167","status":"publish","type":"post","link":"https:\/\/www.vialattea.net\/content\/2167\/","title":{"rendered":"Vorrei sapere che cosa sono e come vengono realizzati i passaggi dei test di\r\nLucas-Lehmer, utilizzati per la ricerca dei numeri primi di Mersenne."},"content":{"rendered":"

Definizioni e
\n propriet\u00e0<\/b><\/font><\/p>\n

Numeri primi<\/i><\/b><\/font><\/p>\n

Nella risposta, vengono date per note le definizioni e
\n propriet\u00e0 dei numeri primi, che possono essere comunque
\n reperite in altra risposta di “Chiedi all’esperto” ai due seguenti links:<\/p>\n

Sui Numeri Primi – risposta di Luca
\n Fini<\/u><\/font><\/a> <\/p>\n

Sui Numeri Primi – risposta di Carlo
\n Consoli
<\/u><\/font><\/a><\/p>\n

Richiamiamo solo brevemente la definizione di numero
\n primo di Mersenne: un numero primo ottenibile come M(n)=2<\/i>n<\/i><\/sup>-1<\/i>
\n \u00e8 detto numero primo di Mersenne<\/i>.<\/p>\n

Funzione MOD
<\/i><\/b><\/font><\/p>\n

La funzione MOD<\/i>, resto<\/i> o modulo<\/i>,
\n \u00e8 definita come il resto della divisione intera.<\/p>\n

x mod y<\/i> pu\u00f2 essere calcolata in due modi:<\/p>\n

    \n
  1. iterativamente, sottraendo y <\/i>da x<\/i>
    \n fino ad ottenere un risultato minore di y<\/i><\/li>\n
  2. mediante la formula \"\" ove \"\"<\/li>\n<\/ol>\n

    \u00e8 la parte intera inferiore di x <\/i><\/p>\n

    Ad esempio:<\/p>\n

    20 mod 8 = 4<\/i><\/p>\n

    iterativamente: 20 \u2013 8 = 12 \u2013 8 = 4<\/i><\/p>\n

    con la formula: 8(2.5 \u2013 2) = 4<\/i><\/p>\n


    \n <\/font><\/p>\n

    Il test L-L<\/b><\/font><\/p>\n

    Il test di Lucas-Lehmer serve per testare la
    \n primalit\u00e0 di un numero primo di Mersenne M(n)=2<\/i>n<\/i><\/sup>-1<\/i>.
    \n M(n) <\/i>\u00e8 primo se e solo se s(n-2) mod M(n) = 0<\/i><\/p>\n

    ove s(n-2) <\/i>\u00e8 l\u2019elemento n-2<\/i> della
    \n successione esponenziale ricorsiva seguente:<\/p>\n

    \"\"<\/p>\n

    In altri termini, M(n)<\/i> \u00e8 primo se divisibile
    \n per il termine s(n-2)<\/i> della successione s(n)<\/i>.<\/p>\n

    Proviamo a calcolare i primi termini di s(n) <\/i>applicandone
    \n la definizione ricorsiva:<\/p>\n

    s(0)=4 <\/i>\u00e8 il valore iniziale<\/p>\n

    s(1) = 2<\/i>s(0)<\/i><\/sup>-2 = 14<\/i> ad
    \n ogni passaggio eleviamo 2 al valore precedente e
    \n sottraiamo due<\/p>\n

    s(2) = 2<\/i>14<\/i><\/sup>-2 = 194<\/i><\/p>\n

    s(3) = 2<\/i>194<\/i><\/sup>-2 = 37634<\/i>
    \n \u2026e cos\u00ec via\u2026<\/p>\n

    Con i termini appena calcolati possiamo testare se M(5)
    \n = 31<\/i> \u00e8 primo. <\/p>\n

    Applichiamo il test e calcoliamo
    \n s(n-2) mod M(n) = s(5-2) mod M(5)<\/i> = s(3) mod M(5)<\/i>
    \n = 37634 mod 31 = 0<\/i><\/p>\n

    M(5) <\/i>\u00e8, quindi, primo.<\/p>\n

    Il problema del test L-L \u00e8 che la successione s(n)<\/i>
    \n diverge con rapidit\u00e0 impressionante (esponenziale<\/i>,
    \n appunto).<\/p>\n

    Gi\u00e0 il termine s(8)<\/i> \u00e8 un numero a 147 cifre
    \n (si dice \u00e8 dell\u2019ordine di 10<\/i>147<\/i><\/sup>):<\/p>\n

    s(8)=26216346504927851452605936955756303
    \n 921364787755952454591190600534955577383
    \n 123693501595628184893342699930798241866
    \n 4943276943901608919396607297585154<\/i><\/p>\n

    La fig. 1 illustra l\u2019entit\u00e0 del fenomeno di
    \n esplosione esponenziale
    \n dell\u2019ordine di grandezza degli elementi di s(n)<\/i>.<\/p>\n

    <\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
    S(n)<\/i><\/b><\/font><\/td>\nOrdine<\/i><\/b><\/font><\/td>\n<\/tr>\n
    \n

    1<\/i><\/font><\/p>\n<\/td>\n

    		\n

    2<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    2<\/i><\/font><\/p>\n<\/td>\n

    		\n

    3<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    3<\/i><\/font><\/p>\n<\/td>\n

    		\n

    6<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    4<\/i><\/font><\/p>\n<\/td>\n

    		\n

    10<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    5<\/i><\/font><\/p>\n<\/td>\n

    		\n

    19<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    6<\/i><\/font><\/p>\n<\/td>\n

    		\n

    38<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    7<\/i><\/font><\/p>\n<\/td>\n

    		\n

    74<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    8<\/i><\/font><\/p>\n<\/td>\n

    		\n

    147<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    9<\/i><\/font><\/p>\n<\/td>\n

    		\n

    294<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    10<\/i><\/font><\/p>\n<\/td>\n

    		\n

    587<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    11<\/i><\/font><\/p>\n<\/td>\n

    		\n

    1172<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    12<\/i><\/font><\/p>\n<\/td>\n

    		\n

    2344<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    13<\/i><\/font><\/p>\n<\/td>\n

    		\n

    4686<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    14<\/i><\/font><\/p>\n<\/td>\n

    		\n

    9372<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    15<\/i><\/font><\/p>\n<\/td>\n

    		\n

    18743<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    16<\/i><\/font><\/p>\n<\/td>\n

    		\n

    37484<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    17<\/i><\/font><\/p>\n<\/td>\n

    		\n

    74967<\/font><\/p>\n<\/td>\n<\/tr>\n

    \n

    18<\/i><\/font><\/p>\n<\/td>\n

    		\n

    149934<\/font><\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    <\/center><\/div>\n

    Fig.1:
    \n Ordine di grandezza degli elementi di s(n)<\/i><\/font><\/p>\n

    s(18)<\/i> \u00e8, quindi, un numero di quasi
    \n centocinquantamila cifre !<\/p>\n

    Una comune calcolatrice scientifica non sarebbe in
    \n grado di operare oltre il quarto elemento di s(n) <\/i>ed
    \n un moderno calcolatore dotato di software apposito inizia
    \n a faticare intorno al ventesimo elemento (e questo \u00e8
    \n anche il motivo per cui la tabella di Fig.1 si ferma ad s(18)<\/i>).<\/p>\n

    Per questo motivo \u00e8 stata ideata una versione
    \n modificata della successione s(n)<\/i> che mantenga le
    \n stesse propriet\u00e0 utili al test di primalit\u00e0:
    \n l\u2019idea \u00e8 di calcolare gli elementi di s(n) <\/i>modulo
    \n M(n)<\/i><\/p>\n

    \u00a0<\/p>\n

    \"\"<\/p>\n

    Nella versione modificata della successione s(n)<\/i>,
    \n i coefficienti possono essere impiegati solo per testare
    \n la primalit\u00e0 di M(n)<\/i> ma, in compenso, il test \u00e8
    \n molto pi\u00f9 veloce.<\/p>\n

    Tra le altre cose, il test termina automaticamente
    \n qualora s(n-2)<\/i> = 0<\/i> perch\u00e9 <\/p>\n

    s(n-2) mod M(n) = 0 mod M(n) = 0<\/i><\/p>\n

    Nella versione modificaa, gli s(n)<\/i> vengono
    \n generati come sopra, salvo applicare il modulo M(n)<\/i>
    \n ad ogni passo.<\/p>\n

    Applichiamo la nuova definizione per calcolare, di
    \n nuovo, il test di primalit\u00e0 di M(5)<\/i>:<\/p>\n

    s(0)=4 <\/i>\u00e8 il valore iniziale<\/p>\n

    s(1) = 2<\/i>s(0)<\/i><\/sup>-2 = 14<\/i> mod
    \n 31 = 14<\/i> come sopra, ma mod 31<\/i><\/p>\n

    s(2) = 2<\/i>14<\/i><\/sup>-2 = 194 mod 31
    \n = 8<\/i><\/p>\n

    s(3) = 2<\/i>194<\/i><\/sup>-2 = 37634<\/i> mod
    \n 31 = 0 s(3) = 0 <\/i><\/p>\n

    e 31 <\/i>\u00e8 un primo di Mersenne.<\/p>\n

    Una propriet\u00e0 interessante dei primi di Mersenne \u00e8
    \n che M(p) <\/i>\u00e8 primo se p <\/i>\u00e8 primo. Ci\u00f2
    \n significa che, poich\u00e9 31 \u00e8 primo, allora anche M(31)<\/i>
    \n deve esserlo.<\/p>\n

    Applichiamo il test per verificare la primalit\u00e0 di M(31)
    \n = 2<\/i>31<\/i><\/sup>-1 = 2147483647 <\/i>e
    \n calcoliamo i 31-2 = 29 <\/i>elementi di s(n)<\/i>,
    \n nella versione modificata:<\/p>\n

    M(31) = 2147483647<\/font><\/p>\n

    s(0) = 4<\/font><\/p>\n

    \n
    \n

    14
    \n 194
    \n 37634
    \n 1416317954
    \n 669670838
    \n 1937259419
    \n 425413602
    \n 842014276
    \n 12692426
    \n 2044502122
    \n 1119438707
    \n 1190075270
    \n 1450757861
    \n 877666528
    \n 630853853
    \n 940321271
    \n 512995887
    \n 692931217
    \n 1883625615
    \n 1992425718
    \n 721929267
    \n 27220594
    \n 1570086542
    \n 1676390412
    \n 1159251674
    \n 211987665
    \n 1181536708
    \n 65536<\/font><\/p>\n<\/blockquote>\n<\/blockquote>\n

    s(29) = 0<\/font><\/p>\n

    E, quindi, M(31) <\/i>\u00e8 primo. <\/p>\n

    Si osservi come il numero di cifre degli elementi s(i)<\/i>
    \n non superi mai il numero di cifre di M(n)<\/i>: questa
    \n propriet\u00e0 \u00e8 sempre vera per definizione di modulo.<\/p>\n

    \u00a0<\/p>\n

    \"\"<\/p>\n

    Fig.2: Ordine di
    \n grandezza degli elementi di s(n)<\/i> modificata<\/font><\/p>\n

    In ascissa \u00e8 il numero n<\/i>, in ordinata
    \n l\u2019ordine massimo dei termini s(n)<\/i>. La figura
    \n 2 illustra, quindi, un andamento quasi-lineare
    \n dell\u2019ordine di grandezza dei termini al crescere di n<\/i>.<\/p>\n

    Ci\u00f2 significa che possiamo tranquillamente procedere
    \n al test di primalit\u00e0 per M(50) <\/i>ed attenderci
    \n calcoli che coinvolgano un numero di cifre pari, al pi\u00f9,
    \n a quelle di M(50) <\/i>stesso, circa 18.<\/p>\n

    \u00a0<\/p>\n

    Alcune considerazioni
    \n conclusive<\/b><\/font><\/p>\n

    Per dare l\u2019idea dei benefici apportati dal test
    \n di Lucas- Lehmer, nella versione modificata, un comune PC
    \n con processore K6-2 a 333Mhz e Mathematica<\/i> \u00e8 in
    \n grado di testare M(200)<\/i>, un numero di 60 cifre (il
    \n fondo-scala della figura 2), in meno di 10 secondi.<\/p>\n

    Testare la primalit\u00e0 di un numero vuol dire
    \n verificarne la non divisibilit\u00e0 per ciascun numero della
    \n serie dei numeri primi che lo precedono ed il Teorema di
    \n Numeri primi asserisce che il numero dei numeri primi
    \n minori o uguali n<\/i> \u00e8 circa n\/log n<\/i>. Ci\u00f2
    \n implica che dovremmo eseguire circa 1058<\/sup>
    \n divisioni per eseguire il test di primalit\u00e0 di M(200)<\/i>.<\/p>\n

    Supponendo di avere un supercomputer in grado di
    \n eseguire un miliardo di divisioni al secondo impiegando
    \n numeri a 60 cifre (roba da fantascienza, almeno ad oggi),
    \n impiegheremmo 1041<\/sup> anni: si parla di miliardi
    \n di miliardi di miliardi di miliardi di anni.<\/p>\n

    Il test di Lucas- Lehmer consente, quindi, di
    \n abbreviare notevolmente i tempi di verifica di primalit\u00e0
    \n dei primi di Mersenne, svicolando l\u2019intrattabilit\u00e0<\/i>
    \n del problema della fattorizzazione.<\/p>\n

    La figura 2 illustra l\u2019ordine di grandezza degli
    \n elementi di s(n) <\/i>modificata.<\/p>\n","protected":false},"excerpt":{"rendered":"

    […]<\/p>\n","protected":false},"author":180,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[67],"tags":[],"class_list":["post-2167","post","type-post","status-publish","format-standard","hentry","category-analisi-numerica"],"_links":{"self":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/2167","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/users\/180"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/comments?post=2167"}],"version-history":[{"count":0,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/2167\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/media?parent=2167"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/categories?post=2167"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/tags?post=2167"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}