La fattorizzazione: un problema difficile anche per un computer

In questo articolo parleremo di un problema di matematica difficile da risolvere anche per un computer (non sto scherzando!) Mi riferisco alla fattorizzazione. Fattorizzare un numero significa scriverlo come prodotto di numeri primi. Per il teorema fondamentale dell’ aritmetica, ogni numero naturale (tranne 0 e 1) può essere scritto in questo modo.

In questo articolo saranno presentati degli esempi con dei numeri piccoli (al massimo di 4 cifre). Se però considerate dei numeri molto grandi (di 250 cifre decimali, ad esempio), il problema diventa quasi impossibile anche per un computer. Per fare un esempio, il seguente numero di 260 cifre non è stato ancora fattorizzato (questo numero è anche chiamato RSA-260):

RSA-260 = 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199

Tornando ad esempi umanamente più accessibili, vi propongo il seguente problema:

Problema 1: Riuscite a fattorizzare il numero 2059? (Suggerimento: 2059 è prodotto di due numeri primi)

Come possiamo risolverlo?

Sembra un problema difficile… (e in effetti lo è!) Nel prossimo articolo parlerò di come risolverlo…intanto posso dirvi che la soluzione è

2059 = 29 x 71

e che il problema “inverso” si risolve molto facilmente (sia per noi esseri umani che per i computer):

Problema 2: Quanto fa 29 per 71?

Per risolvere il Problema 2 basta fare una moltiplicazione in colonna:

Pertanto, servono pochissime operazioni per moltiplicare tra loro due numeri, mentre risulta (apparentemente) impossibile risalire ai due numeri conoscendo soltanto il risultato della loro moltiplicazione.

Perché questo articolo? La difficoltà della fattorizzazione (il Problema 1) e la facilità della moltiplicazione (il Problema 2) sono alla base di uno dei cifrari più diffusi al mondo, l’ RSA (ne parleremo nel dettaglio man mano che andremo avanti con gli articoli). Anche la sicurezza di questo blog è legata ad un numero che ancora non è stato fattorizzato!

Nel prossimo articolo parleremo di alcune strategie possibili per tentare di risolvere il problema della fattorizzazione. Se però avete già qualche idea a riguardo a COME fattorizzare 2059 nel prodotto di 29 e 71, scrivete pure nei commenti. Buona crittografia! xD