Trovare i fattori di un numero intero grande è una impresa assai ardua, e può essere impossibile date le risorse disponibili. Non si conoscono metodi polinomiali per la fattorizzazione, come invece accade per i test di primalità.
Un algoritmo che riceve un intero N, si dice polinomiale se il tempo T(N) che impiega a terminare è esprimibile mediante un polinomio in log(N) (log(N) è a sua volta proporzionale al numero delle cifre di N).
Supponiamo per esempio T(N) = log(N)3/106 secondi, e log(u) = 100. Allora T(u) = 1 secondo. Se log(u) = 200 (raddoppiamo il numero delle cifre) T(u) = 8 secondi, se lo triplichiamo (log(n) = 300) T(u) = 27 secondi e così via.
I migliori algoritmi di fattorizzazione noti non sono polinomiali ma subesponenziali. Il tempo T(n) che impiegano (nel caso peggiore in cui N sia il prodotto di due primi di uguale lunghezza) è proporzionale a
La RSA Security Inc. gestisce una sfida a livello mondiale, ove vengono premiati coloro che fattorizzano gli interi proposti da loro in una particolare lista.
Recentemente, il 3 dicembre del 2003, è stato fattorizzato rsa576 = 188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059
un numero di 576 bit, 174 cifre decimali, prodotto di due primi di 87 cifre:
p = 398075086424064937397125500550386491199064362342526708406385189575946388957261768583317
Le chiavi attualmente utilizzate dall'RSA sono a 1024 bit, 309 cifra decimali. Se indichiamo con T576 il tempo impiegato per fattorizzare rsa576, ricaviamo dalla nostra formula, che T1024 sarà all'incirca 250 milioni di volte più grande di T576.
Come fattorizzare un numero N calcolando le radici quadrate di a mod N
Consideriamo l'equazione
________________
eÖlog(N) log(log(N))
Utilizzando questa formula si vede che se per fattorizzare un numero di 100 cifre occorre un tempo Q, per fattorizzarne uno di 200 il tempo sale a circa 50.000.000 Q, e per 300 arriviamo a 60.000.000.000.000 Q. Se Q è un secondo, per un intero di 100 cifre occorre 1 secondo, per 200 cifre più di un anno e mezzo, per 300 cifre 2 milioni di anni.
q = 472772146107435302536223071973048224632914695302097116459852171130520711256363590397527
Se x1 è una soluzione, lo è ovviamente anche -x1. Per esempio se N = 7 e a = 2, x1 = 4, e -x1 = 3, sono entrambe soluzioni. Le diciamo associate. Se N non è primo la (1) può possedere soluzioni non associate. La
x2 = 1 mod 35
ha due soluzioni non associate: 1 e 6. Naturalmente ce ne sono altre due 34 = -1, associata a 1, e 29 = -6, associata a 6.
Teorema
Se conosco due soluzioni diverse e non associate della (1), sono in grado di trovare due fattori non banali (diversi cioé da 1 e da N) di N.
Dimostrazione
Chiamo x1 e x2 le due soluzioni diverse e non associate che conosco per ipotesi della (1). Allora avrò
x12 = x22 mod N
perché entrambi i quadrati valgono a mod N.
Quindi
x12 - x22 = 0 mod N
N divide x12 - x22
N divide (x1 - x2) (x1 + x2)
Poiché x1 non è associata a x2, x1 è diversa da -x2 mod N, e quindi N non divide A = (x1 + x2)
Poiché x1 è diversa da x2 mod N, N non divide B = (x1 - x2)
Ma N divide, come si è detto, A B.
Dunque una parte di N sta in A, e l'atra parte in B.
Posso trovare i due fattori calcolando i massimi comun divisori:
MCD(N, x1 - x2) e MCD(N, x1 + x2).
Nell'esempio precedente, N = 35, x1 = 1, x2 = 6,
MCD(35, x1-x2) = MCD(35, -5) = 5 e
MCD(35, x1+x2) = MCD(35, 7) = 7.