Versione 1.0
04/09/2014
Pagina 1 di 35
CALCOLO DEL NUMERO DI NUMERI PRIMI π (x)
APPLICANDO LA SERIE ARMONICA
Ing. Pier Franz Roggero, Dott. Michele Nardelli, P.A. Francesco Di Noto
Abstract:
This paper describes the prime counting function that gives the number of primes less
than or equal to x through a formula without using logarithms using instead the
harmonic series.
Also described is a method to calculate the sum of the prime numbers and the n-th
prime number plus various observations.
Versione 1.0
04/09/2014
Pagina 2 di 35
Indice:
1. NUMERO DI PRIMI MINORI O UGUALE a x: (x) APPLICANDO LA SERIA
ARMONICA ......................................................................................................................3
2. CALCOLO APPROSSIMATO DELL’x-ESIMO NUMERO PRIMO px
APPLICANDO LE SERIE ARMONICHE DEI NUMERI NATURALI E QUELLA DEI
NUMERI PRIMI................................................................................................................7
2.1 CALCOLO APPROSSIMATO DELL’x-ESIMO NUMERO PRIMO px
APPLICANDO LA SERIA ARMONICA DEI NUMERI NATURALI...................... 10
3. APPROSSIMAZIONE PER LA SOMMA DEI NUMERI PRIMI .............................11
3.1 CALCOLO DI Sx e Sn ............................................................................................ 13
4. OSSERVAZIONI ........................................................................................................ 17
5. RIFERIMENTI ........................................................................................................... 35
Versione 1.0
04/09/2014
Pagina 3 di 35
1. NUMERO DI PRIMI MINORI O UGUALE a x: π(x) APPLICANDO
LA SERIA ARMONICA
Per ogni numero reale positivo x, si definisce la funzione:
π(x) := numero di primi minori o uguali a x
Il teorema dei numeri primi afferma che:
π(x) ≈
x
ln(x )
Consideriamo la serie armonica Hn definita come la sommatoria infinita delle
frazioni unitarie o, equivalentemente, dei reciproci dei numeri naturali:
∞
Hn= ∑
n =1
1
1 1 1 1 1
=1+ + + + + +…
n
2 3 4 5 6
La serie armonica diverge ma possiamo ricavare delle ottime approssimazioni
della somma dei primi n termini. Si ha che:
∞
Hn= ∑
n =1
1
1
=ln(n)+γ+O
n
n
dove γ è la costante di Eulero –Mascheroni che vale:
Versione 1.0
04/09/2014
Pagina 4 di 35
γ = 0,57721 56649 01532 86060 65120 90082 …
Si ha
ᴨπ(x) ≈
x
H x − kx
Il valore di kx dipende da x ed è sempre un valore frazionario quindi mai
irrazionale o trascendente.
Ad esempio per i primi 14 valori si ha:
TAB. 1:
x
Hx
kx
Hx
2
3
4
5
6
7
8
9
10
11
12
13
14
3/2
11/6
25/12
137/60
49/20
363/140
761/280
7129/2520
7381/2520
83711/27720
86021/27720
1145993/360360
1171733/360360
-1/2
2/6
1/12
37/60
9/20
118/140
201/280
1459/2520
1081/2520
22727/27720
19493/27720
365213/360360
330893/360360
1,500000000
1,833333333
2,083333333
2,283333333
2,450000000
2,592857143
2,717857143
2,828968254
2,928968254
3,019877345
3,103210678
3,180133755
3,251562327
Il valore più basso in assoluto si ha per x=4 dove k4 =
kx
0,500000000
0,333333333
0,083333333
0,616666667
0,450000000
0,842857143
0,717857143
0,578968254
0,428968254
0,819877345
0,703210678
1,013467088
0,918228993
1
= 0,083333333
12
I valori di kx dovrebbero essere compresi nel seguente intervallo:
Versione 1.0
04/09/2014
Pagina 5 di 35
1
= 0,083333333 ≤ kx ≤ 1,7
12
Se scegliamo kx =
8
= 1,6 abbiamo una formula approssimata per calcolare il
5
numero di numeri primi sotto una certa soglia x che va bene per x →∞
Il valore
8
=1,6 è un valore dove la quantità da sottrare ad Hx è un limite oscillante,
5
ovvero il valore da sottrare ad Hx oscilla tra dei valori superiori o inferiori a 1,6 e
di conseguenza il numero di primi sotto una certa soglia ᴨ(x) dà come risultato dei
valori sotto o sopra i valori veri di ᴨ(x).
In questa formula non si utilizzano più i logaritmi e il calcolo è molto più preciso e
più facile.
ᴨπ(x) ≈
x
8
Hx −
5
per x →∞
Versione 1.0
04/09/2014
Pagina 6 di 35
Ecco alcuni valori calcolati con questo nuovo metodo:
TAB 2:
x
π(x)
Hx
π(x) calcolato
10
100
1000
10000
100000
1000000
10000000
100000000
1E+09
1E+10
1E+11
1E+12
1E+13
1E+14
1E+15
1E+16
1E+17
1E+18
1E+19
1E+20
1E+21
1E+22
1E+23
1E+24
1E+25
4
25
168
1,229
9,592
78,498
664,579
5,761,455
50,847,534
455,052,511
4,118,054,813
37,607,912,018
346,065,536,839
3,204,941,750,802
29,844,570,422,669
279,238,341,033,925
2,623,557,157,654,233
24,739,954,287,740,860
234,057,667,276,344,607
2,220,819,602,560,918,840
21,127,269,486,018,731,928
201,467,286,689,315,906,290
1,925,320,391,606,803,968,923
18,435,599,767,349,200,867,866
176,846,309,399,143,769,411,680
2,928968258
5,187377518
7,485470861
9,787606036
12,09014613
14,39272672
16,69531137
18,99789641
21,3004815
23,60306659
25,90565169
28,20823678
30,51082187
32,81340697
35,11599206
37,41857715
39,72116225
42,02374734
44,32633243
46,62891752
48,93150262
51,23408771
53,5366728
55,8392579
58,14184299
7,52
27,88
169,91
1221,36
9532,76
78169,42
662457,35
5747821,32
50760180,65
454482103,98
4114269441,70
37582347460,19
345891239053,79
3203751519541,31
29836503070398,70
279184735845935,18
2623214878502294,35
24737934155116852,16
234047703869348937,70
2220795113619688897,19
21127577715596302359,69
201474439470462063218,20
1925421760941143692208,17
18436830419835076688982,50
176860170648639834865064,41
Versione 1.0
04/09/2014
Pagina 7 di 35
2. CALCOLO APPROSSIMATO DELL’x-ESIMO NUMERO PRIMO
px APPLICANDO LE SERIE ARMONICHE DEI NUMERI
NATURALI E QUELLA DEI NUMERI PRIMI
Consideriamo la serie armonica dei numeri primi Pn definita come la sommatoria
infinita delle frazioni unitarie o, equivalentemente, dei reciproci dei numeri primi
∞
Pn = ∑
n =1
1 1 1 1 1 1
= + + + + +…
pn 2 3 5 7 11
La serie armonica dei numeri primi diverge ma anche in questo caso possiamo
ricavare un’ottima approssimazioni della somma dei reciproci dei numeri primi
inferiori ad una certa soglia x. Si ha che:
x
Px=
∑
pprime
1
=ln ln(x)+M+o(1)
p
Sommiamo la serie armonica e quella armonica dei numeri primi Hx+2Px,
otteniamo
1
x*(Hx+Px) = x*{ln(x)+γ+O +lnln(x)+M+o(1)}=
x
1
x*{ ln(x)+ lnln(x)+0,8387128777+O +o(1)}
x
dove M è la costante di Meissel-Mertens :
M = 0,2614972128…
γ +M=0,8387128777…
Versione 1.0
04/09/2014
Pagina 8 di 35
Siccome:
px =x*{ln(x)+ lnln(x)-1+o(
allora si ha:
x*(Hx+Px) = px+1,8*x
px ≈ x*{Hx+Px -1,8}
1
)}
(ln x ) 2
Versione 1.0
04/09/2014
Pagina 9 di 35
Ad esempio si ha:
x=2*1017
px = 8.512.677.386.048.191.063
Hx= 40,41430943
Px= 3,946295695
px ≈ 2*1017 *(40,41430943+3,946295695-1,8)=2*1017
8.512.121.025.000.000.000
Le prime 4 cifre sono uguali e si ha un errore dello 0,0065%
*(42,560605125)
=
Versione 1.0
04/09/2014
Pagina 10 di 35
2.1 CALCOLO APPROSSIMATO DELL’x-ESIMO NUMERO PRIMO px
APPLICANDO LA SERIA ARMONICA DEI NUMERI NATURALI
Un’altra approssimazione molto valida un po’ meno precisa ma più facile dove non
si calcola Px ma solo Hx è la seguente:
px ≈ x*{Hx+2,2}
px ≈ 2*1017 *(40,41430943+2,2) = 8.522.861.886.000.000.000
Il valore è superiore a quello vero e le prime 2 cifre sono uguali. L’errore è pari allo
0,1196%.
Questo metodo di calcolo è quindi meno preciso del precedente.
Versione 1.0
04/09/2014
Pagina 11 di 35
3. APPROSSIMAZIONE PER LA SOMMA DEI NUMERI PRIMI
La somma dei numeri primi da 2 fino ad x si può calcolare col trucchetto di Gauss
Ad esempio per calcolare la somma dei primi 9 numeri primi:
2+3+5+7+11+13+17+19+23 +
23+19+17+13+11+7+5+3+2 =
25+22+22+20+22+20+22+22+25=
2*(25+22+22+20)+22
Possiamo considerare che approssimativamente si abbia:
22*9/2=99
mentre il valore esatto è 100.
La formula approssimata è la seguente:
x
∑
Sx ≈
pprime
1
x2
≡
p 2[ln( x ) − 0,5]
Si ha anche che il valore è più piccolo rispetto al valore vero di Sx per x→∞
x
∑
pprime
1
x2
>
per n→∞
p
2[ln( x ) − 0,5]
Versione 1.0
04/09/2014
Pagina 12 di 35
La formula che invece da l’n-esima somma di n numeri primi è invece data da:
n
Sn ≈ ∑
k =1
1 n 2 [ln(n ) + 1]
=
pk
2
Si ha anche che il valore è più grande rispetto al valore vero di Sn per n→∞
n
∑
k =1
1
n 2 [ln(n ) + 1]
<
per n→∞
pk
2
Versione 1.0
04/09/2014
Pagina 13 di 35
3.1 CALCOLO DI Sx e Sn
Proviamo a calcolare S(x=100) e S(n=25) rispetto ai valori veri segnati subito di
seguito alle formule approssimate:
x
S100=
∑
pprime
S25=
1
1002
≡
= 1217,97…. S100=1060
p 2[ln(100) − 0,5]
252 [ln(25) + 1]
= 1318,39…. S25=1060
2
Entrambi i valori sono superiori ai valori veri.
Versione 1.0
04/09/2014
Pagina 14 di 35
Proviamo a calcolare S(x=1000) e S(n=168)
x
S100=
∑
pprime
1
1000 2
≡
= 78030,44…. S1000=76127
p 2[ln(1000) − 0,5]
168 2 [ln(168) + 1]
S168=
= 86421,37…. S168=76127
2
Entrambi i valori sono ancora superiori ai valori veri.
Versione 1.0
04/09/2014
Pagina 15 di 35
Proviamo a calcolare S(x=1.000.000) e S(n=78.498)
x
S1000000=
∑
pprime
1
1000000 2
≡
= 37.550.193.649,98…. S1000000=37.550.402.023
p 2[ln(1000000) − 0,5]
78498 2 [ln(78498) + 1]
S78498=
= 37.806.029.737,73…. S78498=37.550.402.023
2
Solo il secondo valore è superiore al valore vero, mentre il primo è per difetto come
dimostrano le formule per n→∞
Versione 1.0
04/09/2014
Pagina 16 di 35
Proviamo a calcolare S(x= 1.299.709) e S(n= 100.000)
x
S1299709=
∑
pprime
1
1299709 2
≡
= 62.206.765.026,94…. S1299709=62.260.698.721
p 2[ln(1299709) − 0,5]
100000 2 [ln(100000) + 1]
S100000=
= 62.564.627.324,85…. S100000= 62.260.698.721
2
Anche in questo caso il secondo valore è superiore al valore vero, mentre il primo è
per difetto come dimostrano le formule per n→∞
Versione 1.0
04/09/2014
Pagina 17 di 35
4. OSSERVAZIONI
In passato si sono fatte stime approssimative di π (N) e dell’n°- numero primo
con n° ≈ n*ln) tramite i logaritmi, naturali ln (n)o meglio ancora integrali Li(n),
vedi il TNP e sue conseguenze. La nostra proposta è invece una originale novità,
in quanto si basa sulla serie armonica, che permette di ottenere risultati altrettanto
buoni, come vedremo nelle successive tabelle, con una sorta di correzione che
diminuisce le differenze tra valore stimato e valore reale di π(N)con N = potenze di
10. Ricordiamo che il calcolo preciso si ottiene con la funzione zeta, la funzione
scalino J(x) ecc. come da Tabella riepilogativa a pag. 359 del libro di J.
Derbyshire “L’ossessione dei numeri primi”(Bollati – Boringhieri. Rif. 2) che
riportiamo nelle note finali, insieme ad altre poche pagine interessanti riguardanti
l’argomento “conteggio dei numeri primi” , e cioè π(N).
Tutti gli altri calcoli sono solo scorciatoie più o meno valide per ottenere valori
approssimativi di π(N) Il nostro calcolo è soltanto una di queste scorciatoie, nuova
ma efficace, poiché ci permette risultati simili a quelli ottenuti con il logaritmo
integrale Li(N), risparmiandoci i complicati calcoli sui quali si basa la Tabella
riepilogativa sopra accennata. Qui di seguito facciamo un tentativo, peraltro
Versione 1.0
04/09/2014
Pagina 18 di 35
riuscito, di miglioramento del precedente calcolo con la serie armonica,
introducendo il concetto e il calcolo di un “correttore medio” che avvicina le
precedenti stime di π(N) = π(10^n) a valori non molto distanti da quelli ottenuti
tramite il logaritmo integrale Li(N), come vedremo riportando qualche tabella
presa dal Web ( Keith Devlin, “La distribuzione dei numeri primi, Rif. 3.
Tentativo con c = rapporto successivo π(N) reale e π(N)’ stimato, come numero
correttore tale che π(N)’ *c ≈ π(N) reale con maggiore precisione
TABELLA 1
N = 10^n
10
100
1000
10000
100000
1000000
10000000
100000000
Totale c
π(N) reale
b
4
π(N)’ stimato
c
7.52
c = rapporto
crescente b/c
0,53
25
168
1,229
9,592
78,498
664,579
5,761,455
27,88
169,91
1221,36
9532,76
78169,42
662457,35
5747821,32
0,8967
0,9887
1,0062
1,0556
1,0042
1,0032
1,0023
6, 9559
c come correttore medio per tutti i valori di c:
c medio =
osservazioni
C cresce fino a
1,0062,poi
decresce
e
tende a 1
Versione 1.0
04/09/2014
Pagina 19 di 35
0,8967 + 0,9887 +1,0062 + 1,0556 + 1,0042 + 1,0032 + 1,0023)/7 = 6,9559/7= 0,9937
minore di 1, quindi poco utile per la correzione, essendo il valore reale
sempre maggiore di quello calcolato a partire da 1229; quindi prendiamo solo la
media dei valori di c maggiori di 1 per calcolare c medio:
c medio = 1,0062 + 1,0556 + 1,0042 + 1,0032 + 1,0023)/5 = 1,004292
Ora, moltiplicando i valori calcolati con le serie armoniche per questo valore
medio, avremmo una nuova tabella con stime migliori di π(N)’ stimato, quindi
con differenze minori con π(N) reale. Cominciamo quindi da 1229, con c medio
maggiore di 1
TABELLA 2
π(N)’ stimato c medio
con la serie
armonica
a
b
Prodotto
π(N) reale
a*b = π(N)””
Differenza
intera
d–c
nuova stima c
d
differenza
precedente
d-a
1221,36
1,229
1,004292
1226,60
3 = 1229 -1226
8= 1229 - 1221
Versione 1.0
04/09/2014
Pagina 20 di 35
9,592
1,004292
9573,67
19
60
9532,76
1,004292
78504,92
-6
78,498
329
78169,42
1,004292
665300,61
-721
664,579
2122
662457,35
1,004292
5772490,96
-11035
5,761,455
13634
5747821,32
Come possiamo vedere, le nuove
differenze, d – c, sono minori della vecchie
differenze d – a, e quindi questa correzione con c medio è molto utile e
interessante a partire da 78169,42 (colonna a) , le nuove differenze sono
negative ma più piccole come valore assoluto, mentre le vecchie
rimangono positive.
Dal link :
Versione 1.0
04/09/2014
Pagina 21 di 35
www.matmedia.it/biblioteca/.../la-distribuzione-dei-numeri-primi.html
“Distribuzione dei numeri primi”
riprendiamo la tabella con le stime di π(N) = π(10^n) in base a Li(N)
TABELLA 3
n
p(n)
1000
10000
100000
1000000
10000000
100000000
168
1229
9592
78498
664579
5761455
Li(n)
172
1231
9588
78534
665138
5769341
145
1086
8686
72382
620420
5428681
178
1246
9630
78628
664918
5762209
Ora confrontiamo la nostra stima corretta con c medio e la stima con Li(n)
rispetto ai valori reali
TABELLA 4
Valori reali di
π(N) = π(10^n)
a
Stima con c medio
Li(n)
Differenze intere
b
c
b–a
c-b
c-a
Versione 1.0
04/09/2014
Pagina 22 di 35
178
168
1226,60
-3
1246
1229
c – a = 10
20
17
9573,67
-19
9630
9592
57
38
78504,92
78498
6
78628
124
130
665300,61
721
-382
664579
664918
339
5772490,96
11035
5761455
5762209
-10281
754
Versione 1.0
04/09/2014
Pagina 23 di 35
Come possiamo osservare, le differenze c – b (confronto tra Li(N), c – a)) e le
nostre stime con c corretto) sono paragonabili tra loro, almeno fino a 10^7, e
quindi le nostre stime sono abbastanza attendibili. Possiamo provvisoriamente
concludere che le nostre stime basate sulla serie armonica, sia pure corrette con c
medio, sono molto simili tra loro. Insomma, forse, Hn batte Li(n), o poco ci
manca.
Qui di seguito la pag. 359 con la tabella al calcolo preciso di π (1 000 000) =78498
seguita da altre pagine dello stesso libro di Derbyshire, anch’esse riguardanti il
calcolo di π(N)
Versione 1.0
04/09/2014
Pagina 24 di 35
Versione 1.0
04/09/2014
Pagina 25 di 35
Versione 1.0
04/09/2014
Pagina 26 di 35
Versione 1.0
04/09/2014
Pagina 27 di 35
NOTA 1
Sull’accenno al conteggio dei numeri primi, a B. Riemann e alle possibili
conseguenze dell’ipotesi di Riemann.
Nella 4° di copertina del libro di John Derbishire, leggiamo che:
“ Nell’agosto 1859 Bernhard Riemann, matematico giovane e ancora poco
noto, presentò all’accademia di Berlino un articolo intitolato Sul numero dei
Versione 1.0
04/09/2014
Pagina 28 di 35
primi minori di una certa grandezza . In quella circostanza discusse pr la
prima volta l’ipotesi che prende il suo nome è passata alla storia come uno
di più famosi problemi irrisolti della matematica. Dimostrare questa ipotesi
permetterebbe di trovare una formula per generare l’elenco dei numeri primi,
cosa che avrebbe conseguenze fondamentali non solo per la scienza
matematica, ma anche per la fisica quantistica e per la sicurezza
informatica...”
Nostro commento
Siamo d’accordo per le conseguenze in matematica e fisica quantistica,
ma non per la sicurezza informatica. Abbiamo già elenchi lunghissimi di
numeri primi, che però non aiutano affatto eventuali violazioni della
crittografia RSA basata sui numeri primi e numeri RSA come prodotti
di due numeri primi lunghi qualche centinaio di cifre. Occorrerebbero
elenchi di coppie di numeri primi, come per esempio le coppie di numeri
primi gemelli, le coppie di Goldbach o dei numeri di Sophie - Germain,
ecc. con rispettivi rapporti r = q/p di circa 1, variabile tra 1 e 2,25, e di
circa 2. Escludiamo i prodotti tra di due numeri gemelli, facilmente
fattorizzabili con l’algoritmo di Fermat a ritroso, e i prodotti di due
Versione 1.0
04/09/2014
Pagina 29 di 35
numeri di Sophie - Germain, poiché ad un rapporto r di circa 2
corrisponde una percentuale di p rispetto ad n = √N pari a circa il 70%
di n, e quindi anch’esso facilmente fattorizzabili.
Prendiamo invece le coppie di Goldbach per un intero pari N come
somma N = p + q , disposte in due colonne, la prima con valori crescenti
di p da 3 fino ad N/2 e la seconda con valori decrescenti da N fino a N/2
Se a destra di tali coppie scriviamo i prodotti N’ = p*q, notiamo che i
prodotti crescono ( mentre la somma ovviamente rimane costante, N, per
tutte le coppie. I prodotti invece crescono fino al quadrato della
semisomma s, e cioè fino ad s^2. I rapporti q/s invece diminuiscono fino
ad 1 (p = n = q, con q/n = n/n = 1). Ma dal 66,6% di n tali rapporti
variano da 2,25 a 1 (o pochissimo in più per le coppie di gemelli, per es.
103/101 = 1,019...), e quindi possono riguardare i numeri RSA N’,
prodotti di tali coppie di Goldbach. Questo significa che p è superiore
al 67% di n ed è quindi inutile cercarlo prima. Il tempo di
fattorizzazione di qualsiasi numero RSA quindi si riduce ad un terzo di
quello previsto: per esempio, se si prevedono 1000 anni per fattorizzare
un certo numero RSA, applicando questo ostro teorema, ne
basterebbero “soltanto” 1000/3 = 333, 33.... Non è molto, ma nemmeno
Versione 1.0
04/09/2014
Pagina 30 di 35
poco. Inoltre esistono già metodi di fattorizzazione basati sulla possibile
verità della RH, ma non in grado di violare la crittografia RSA.
Quindi la RH e il suo possibile elenco di singoli numeri primi sono
pericolosi per la crittografia RSA, come molti credono. Il pericolo caso
mai potrebbe venire da teoremi riguardanti coppie di numeri primi,
come quelle sopra accennate, i cui prodotti N’=p*q come numeri RSA
potrebbero benissimo essere evitati dalle Società crittografiche (cosa che
consigliamo nei nostri lavori) per non facilitare la loro fattorizzazione,
cosa ovviamente pericolosa per la sicurezza informatica. I prodotti delle
coppie di Goldbach possono solo ridurre di 2/3 i tempi di calcolo.
Piccolo esempio pratico per N = 60:
TABELLA 5
p
q
N=p+q
(congettura
Goldbach)
N’ = p*q
di r = q/p
percentuale di
rispetto ad n
= 1/√r
7
53
60
371
p
Versione 1.0
04/09/2014
Pagina 31 di 35
7,57
0,36 =36%
13
47
60
611
3,61
0,52 =52%
17
43
60
731
2,52
0,62 = 62%
19
41
60
779
2,15
...68%
23
37
60
851
1,60
... 79%
29
31
60
899
Versione 1.0
04/09/2014
Pagina 32 di 35
1,068....
... 96%
29 e 31 gemelli
Ultima coppia di
Goldbach
per
molti N multipli di
12, per es.
60 = 5*12
30
30
60
900
1
Come vediamo, il rapporto r =q/p inferiore a 2,25 è 2,15, da qui
comincia la “zona rossa” o “zona RSA” che comprende N’ = p*q e p
compreso tra il 67% di n = s^2 , in questo caso 30 = √900, con N’ come
possibili numeri RSA, in questo caso 779, 851, 899 e possibili p 19, 23
e 29 ; p minimo 19, circa il 68% della radice quadrata di 779
(infatti √779= 27,91
e 27,91*0,68 = 18,97 ≈ 19 ) e circa il
19/0,3 = 63,33% di 30 = semisomma. E così via.
Se si costruissero tabelle simili con numeri primi p e q di circa 300 cifre,
come nei numeri RSA di tipo RSA – 2048 (che dal 2014 sostituiranno
per prudenza tutti quelli più piccoli usati finora), occorrerebbero
Versione 1.0
04/09/2014
Pagina 33 di 35
miliardi e miliardi di righe, ma la zona rossa sarebbe sempre
compresa tra il 66,666 ≈ 67% di s = semisomma (p + q)/2 con
N = p + q per la congettura di Goldbach.
Di chiaro, comunque, sulla relazione tra elenchi di coppie di numeri
primi e fattorizzazione, c’è ancora solo questo, che non è molto; mentre
l’ipotesi di Riemann , con il suo supposto elenco infinito di numeri primi
singoli, non sembra entrarci affatto con una possibile violazione della
crittografia RSA, pur essendo importante per altri rami della
matematica o della fisica quantistica.
Questo per dire che, per quanto riguarda una fattorizzazione più veloce
e in grado di preoccupare la crittografia RSA, con l’ipotesi di Riemann
non si è ancora cavato un ragno dal buco, mentre con la ex –congettura
di Goldbach, unita al nostro Teorema fondamentale della fattorizzazione
veloce (Rif. 4), abbiamo eliminato i due terzi dei tempi di calcolo per la
fattorizzazione classica (detta a forza bruta) dei numeri RSA,
eliminando i primi sue terzi dei numeri primi fino ad n = √N’.
Se poi utilizziamo l’algoritmo di Fermat a ritroso (N’ + d^2 = s^2, da cui
poi p = s – d e q = s + d , il risparmi di tempo potrebbe ancora ridursi
Versione 1.0
04/09/2014
Pagina 34 di 35
ulteriormente.
Ma l’ipotesi di Riemann è invece utilissima ne nella funzione conteggio
dei numeri primi fino ad N, e cioè π(N) = π(10^n), oggetto di questo
lavoro basato però sulla la serie armonica Hn , con risultati vicinissimi,
come abbiamo visto, a quelli ottenuti con Li(N).
Versione 1.0
04/09/2014
Pagina 35 di 35
5. RIFERIMENTI
1)Wikipedia
2) “J. Derbyshire, “L’ossessione dei numeri primi” , Bollati Boringhieri
3) Articolo di Keith Devlin, La distribuzione dei numeri primi, sul sito di Polymath
Link
www.matmedia.it/biblioteca/.../la-distribuzione-dei-numeri-primi.html
4) Teorema fondamentale della fattorizzazione veloce (TFF), sul nostro sito
http://nardelli.xoom.it/virgiliowizard/
© Copyright 2024 ExpyDoc
