Teorema fondamentale della Fattorizzazione Veloce

IL TEOREMA FONDAMENTALE
DELLA FATTORIZZAZIONE
Gruppo “B.Riemann”*
Francesco Di Noto, Michele Nardelli
*Gruppo amatoriale per la ricerca matematica sui numeri primi, sulle loro congetture e sulle
loro connessioni con le teorie di stringa.
Abstract
In this paper we show our Fundamental Theorem about
factorization
Riassunto
In questo lavoro esponiamo il nostro Teorema Fondamentale
della fattorizzazione, basato sulle progressioni geometriche,
poiché p, n e q fanno parte di una progressione geometrica con
numero fisso √r = √q/p, con n =√N e con N = p*q, essendo p e
q simmetrici rispetto ad n.
Ma anche, equivalentemente, come progressione geometrica ,
p*√r = n
1
n*√r = q
e quindi, di conseguenza,
p*r = q
Ovviamente non conosciamo a priori p e q (è proprio la
ricerca di p e q, conoscendo solo N, lo scopo della
fattorizzazione). Cercare √r per altre vie è quindi un
problema matematico equivalente alla fattorizzazione veloce.
Per il momento non si conosce nessuna valida via alternativa,
tuttavia…
°°°°°°°°°
Il nostro Teorema si può enunciare in questo modo:
p, n=√N con N = p*q e q fanno parte di una terna di
termini di una progressione geometrica con numero fisso
(ratio) √r =√p*q, di modo tale che
p = n/√r
q = n*√r”
p*r = q
2
Dimostrazione
Tutti i matematici sanno che cos’è una progressione
geometrica, con numero fisso r . Ora prendendo una terna
a, b, c qualsiasi di una progressione geometrica qualsiasi, e
conoscendo r, è facilissimo fattorizzare il prodotto dei due
termini esterni della terna, estraendo la radice quadrata b e
ottenendo a = b/√r e c = b*√r : nella fattorizzazione si usano
però i termini equivalenti p = a, n = b e q = c.
Tale Teorema nasce dalla simmetria di p e q rispetto alla
semisomma s = (p + q)/2 , tramite la semidifferenza
(q-p)/2 = d, da cui poi p = s - d e q = s + d (e quindi è coinvolta
la congettura di Goldbach, che riteniamo vera, anche se
ancora non ufficialmente dimostrata: il matematico
australiano Terence Tao ha annunciato la sua prossima
pubblicazione della congettura debole di Goldbach (N’
dispari come somma di tre numeri primi); ma poi,
possibilmente, il passo alla dimostrazione della congettura
3
forte sarà breve (N pari come somma di due numeri primi,
per tutti i numeri pari N > 4; per i numeri dispari N’ deve
essere N > 7)). Infatti , prendiamo
p=s-d e q=s+d
valide per qualsiasi progressione aritmetica; se però in tali
formule cambiamo il segno - in / e il segno + in *, s da
semisomma in radice quadrata e la somma S = p + q in
prodotto N = p*q, s in radice quadrata del rapporto √r con
r = q/d, avremo:
p = n /√r e
q = n*√r
alla base del nostro teorema. Abbiamo trasformato le formule
p=s-d e q=s+d
(1)
valide per le progressioni aritmetiche, in formule omologhe
per le progressioni geometriche:
p = n /√r e
q = n*√r
Facciamo ora qualche breve e semplice esempio:
4
Progressione aritmetica con numero fisso 2:
2, 4, 6, 8, 10, 12,
14,… e prendiamo la terna 6, 8, 10; 8
e il termine centrale, ed è la media aritmetica tra 6 e 10
(termini esterni) poiché (6+10)/2 = 16/2 = 8, ma abbiamo anche
somma S = 6 + 10 = 16, e semisomma s = 16/2 = 8; differenza
10 - 6 = 4 e semidifferenza d = 4/2 = d, da cui, con le formule
(1), abbiamo:
6 = 8 - 2 e 10 = 8 + 2 = 10, ritornando alla terna prescelta
6, 8, 10, con 6 e 10 simmetrici aritmeticamente rispetto a 8
cioè con differenze uguali: 8 – 6 = 2 e 10 – 8 = 2
(Un esempio per la congettura di Goldbach per N =10
come somma di 3 + 7 e di 5 + 5; 3 e 7 sono simmetrici
rispetto a N/2 = 10/2 = 5, infatti 3 = 5 - 2 e 7 = 5 + 2 , mentre
5+ 0 = 5 e 5 - 0 = 5 I numeri primi p e q tali che S = p + q = N
sono simmetrici rispetto alla loro semisomma s = (p+q)/2 =N/2,
tramite la semidifferenze ( d = q - p), e questo vale per tutti i
numeri pari N e tutte le coppie di numeri primi p e q con
5
somma N; noi, come gran parte dei matematici moderni,
riteniamo vera la congettura di Goldbach).
Ora trasformiamo la suddetta progressione aritmetica in
progressione geometrica con numero fisso 2:
2, 4, 8, 16, 32, 64,
128,…; prendiamo ora la terna
16, 32, 64 e applichiamo le formule (2) per le progressioni
geometriche
p = n /√r e
q = n*√r
poiché abbiamo ora p = 16, n =32= √1024 e q = 64,
N = 16*64 = 1024, r= 64/16 = 4, √r = √4 = 2, per sostituzione
nelle (2) abbiamo 16 = 32/2, 64 = 32*2 , ritornando alla terna
originaria 16, 32, 64, ; lo stesso risultato si ottiene ovviamente
con qualsiasi altra terna della stessa progressione geometrica.
(Notiamo che 8, 16 e 64 sono tutti numeri divisibili per 8 che
corrisponde ai numeri di modi di vibrazione fisica delle
superstringhe, esprimibile attraverso la seguente equazione di
6
Ramanujan:
∞ cos πtxw'


− πx 2 w '
e
dx 
∫

142
0 cosh πx
4 anti log
⋅ 2
πt 2
t w'
w'
−

e 4 φw' (itw') 
1 
8=
.)
3
  10 + 11 2 
 10 + 7 2  
+ 

log  



4
4
 




In questo caso otteniamo risultati esatti perché il rapporto
r = q/p è un quadrato perfetto (4) e la sua radice quadrata è
quindi un numero intero (2). Ma tale rapporto non è sempre
un quadrato perfetto, e quindi la sua radice quadrata è un
numero decimale, ma dà ugualmente un risultato quasi
perfetto.
Per esempio per p=127, n = 170,53 e q = 229, N =
127*229=29083, r = 229/127 = 1,80314960629… e
√r =1,34281406244
Sostituiamo alle (2) e avremo
p ≈ 170,53/1,34281406244 = 126,994499662 ≈ 127
q ≈ 228,990082067 ≈ 229 (cioè 170,53 * 1,34281406244)
In questi casi, basta arrotondare alla cifra intera successiva
per avere i valori esatti di p e q. Il problema è che non
7
conosciamo ancora p e q, e quindi nemmeno il loro rapporto r
e √r, da ricercare con altre vie.
Una, possibile solo per alcuni casi (rapporto r molto
basso e prossimo a 1), funziona con buona approssimazione e
solo per tali rapporti bassissimi. Ma per rapporti leggermente
più alti non funziona più o meno bene, (vedi Ipotesi
percentuale in Rif. 1); ma è ancora tutta da dimostrare,
tuttavia fornisce un qualche utile appiglio, una volta
dimostrata (ma è difficile), per trovare r anche molto
approssimativo, ed eliminare buona parte dei tempi di calcolo.
Tale ipotesi dice che la percentuale di p rispetto ad n può
essere di circa le due prime cifre decimali della radice
quadrata di N.
Per esempio,
per il numero N 29083= 127 * 229 sopra visto, la radice
quadrata è 170, 53, con p approssimativo al 53% di n :
p ≈ 53% di 170, 53 = 170,53*0,53 = 90,3809, e per trovare
8
p = 127 occorre cercarlo dopo 90 , risparmiando i tempi di
calcolo da p = 3 a p = 90. La vera percentuale è però circa il
74% di n, poichè 127/1,70 = 74,70, e
170,53*0,7470 = 127,38591.
C’è quindi una differenza di 74 – 53 = 21% tra la
percentuale stimata e quella reale, almeno in questo esempio.
Ma si risparmia già il tempo di calcolo fino a 90; e questo è un
caso già attendibile in qualche misura, di solito non è così, ma
anche peggio.
Una futura nostra dimostrazione della nostra ipotesi
percentuale (partendo dalla congettura di Legendre e da una
sua conseguenza che sembra essere coinvolta nella formazione
della parte decimale) potrebbe ridurre tali divergenze,
(sempre più piccole al decrescere del rapporto p/q); ma al
massimo del 2% - 3% ma non di più: comunque non ancora
abbastanza per permettere di violare la crittografia RSA. (Per
maggiori dettagli, Rif.1).
9
Una progressione quasi perfetta è la serie di Fibonacci, dove si
verifica il relativo paradosso: presa una terna di Fibonacci,
per es. 8, 13, 21 il quadrato di 13 è 169 = 168 = 169 -1: se si
prende la terna successiva. 13, 21 34, abbiamo 21*21 = 441
mentre 13*34 = 442 =441 +1, e 1 e -1 si alternano all’infinito
per tutte le terne successive; poiché sappiamo che il rapporto
in genere è r = 2,617924 e √r = √2,617924 = 1,618 , si
possono applicare le (2) per avere 13 e 34:
21/1,618 = 12,97 ≈ 13 e 21*1,618 = 33,978 ≈ 34, com’è gia noto
ai matematici.
Il problema principale, quindi, resta sempre quello di trovare
r con buona approssimazione, sia con la futura ma difficile
dimostrazione della nostra ipotesi percentuale sia anche,
eventualmente, per altre possibili vie alternative.
Qui un esempio di utile applicazione della nostra ipotesi
percentuale per p e q molto vicini:
N = 13 068 221 = 3613*3617 è un prodotto di tali numeri, in
10
questo caso cugini (differenza 4) è facile fattorizzarlo con i
computer, ed in particolar modo con l’algoritmo di
fattorizzazione alla Fermat; ma se volessimo fattorizzarlo a
mano occorrerebbe moltissimo tempo, provando tutti i
numeri primi fino a poco meno della sua radice quadrata
n = 3614,99944: la parte decimale di n, e cioè 0,99944…
tradisce la piccola differenza (4), poichè i suoi fattori sono
3613 e 3617, con differenza 4, con 3613 vicinissimo ad n, e in
tal caso conviene tentare la fattorizzazione a ritroso, dalla
radice quadrata ai numeri primi più vicini; ponendo n
intero = 3615, basta provare col numero dispari inferiore e
anche primo (3613), e scoprire che è il valore reale di p
cercato, poiché divide N = 13 068 221.
Il rapporto reale r = q/n è infatti molto basso, r = 3617/3613=
1,0011… e la sua radice quadrata è √ 1,001107 = 1,000553,
da cui poi 3614,99/1,000553 = 3612,992 ≈ 3613 = p e
3614,99 *1,000553 = 3616,989 ≈ 3617 = q, il tutto sfruttando
11
velocemente la nostra ipotesi percentuale per questi casi in cui
funziona.
Resta da capire perché tale metodo funziona sempre per
differenze q - p molto piccole, e quindi con rapporti molto
bassi, e raramente per differenze maggiori e rapporti un po’
più alti.
Questo fenomeno sarà studiato meglio in futuro,
possibilmente anche da noi, ma dopo un’eventuale , ma molto
difficile, nostra o altrui dimostrazione della nostra ipotesi
percentuale.
Questo Teorema Fondamentale sulla fattorizzazione veloce
potrebbe sicuramente contribuire alla dimostrazione
dell’ipotesi percentuale, e solo allora la fattorizzazione
potrebbe essere finalmente essere chiamata “veloce”,
permettendo di risparmiare più del 90% dei tempi di
calcolo attuali. Niente più secoli ne tanto meno millenni, ma
solo qualche anno, e (nei casi di numeri RSA con sole alcune
12
decine di cifre o anche 100 o poco più) anche qualche mese, al
massimo qualche giorno, oppure, come scrisse Marcus du
Sautoy, (nel suo libro “L’enigma dei numeri primi” Rizzoli)
“17 anni in 17 minuti”.
Un corollario/conseguenza di questo teorema è che, per
rapporti r ≈ q/p ≈ 2, come mediamente succede nei numeri
RSA (r mediamente variabile da 1 a 2,3) p è composto dalla
metà di cifre del numero N, e quindi è inutile cercarlo tra i
numeri primi con un numero inferiore di cifre, come forse si
fa ancora adesso, sia pure con potentissimi computer.
Se il numero di cifre c è dispari, allora il numero di
cifre di n e di p è (c + 1)/2 ; infatti tutti i numeri RSA già
fattorizzati hanno tale caratteristica, comune anche ai numeri
RSA non ancora fattorizzati (e difficilmente lo saranno, poiché
i relativi premi sono già stati ritirati).
Tuttavia, in Rif. 2 proponiamo una possibile e fattibile
fattorizzazione del numero RSA - 2048 in tempi ragionevoli
13
supponendo che il numero p sia circa la metà di q, come
media approssimativa tra n/2 ed n, corrispondente
ad una percentuale tra il 70% e il 72% di n = √N con
N = RSA -2048.
Riferimenti
1) “Ipotesi su p < n come possibile percentuale di n = √N
per una fattorizzazione più veloce”
Francesco Di Noto, Michele Nardelli
(Gruppo “B.Riemann”)
2) “- Numero RSA - 2048: una previsione sulla stima
approssimativa dei suoi fattori p e q – “ (di prossima
pubblicazione)
Francesco Di Noto, Michele Nardelli
(entrambi su questo sito)
14