Nell’ articolo del 29 marzo abbiamo parlato di quanto sia difficile fattorizzare un numero, ovvero scriverlo come prodotto di numeri primi. Abbiamo visto che anche nel caso di numeri piccoli, ad esempio 2059, la ricerca di un algoritmo per la fattorizzazione sembra un’ impresa da Mission Impossible. Oggi inizieremo a scavare più a fondo nella vicenda.
L’ algoritmo di cui parleremo oggi è chiamato metodo a forza bruta (o brute force, se usiamo l’ inglese). Questo algoritmo ha un pregio enorme e un difetto ancora più grande:
Il pregio del metodo brute force: è semplicissimo se paragonato con gli altri algoritmi di fattorizzazione.
Il difetto del metodo brute force: è lentissimo. Non troverete mai un algoritmo di fattorizzazione più lento della brute force. In più sono veramente pochi i casi in cui ha senso applicare questo metodo, e proseguendo con l’articolo capiremo il perché.
Prendiamo il numero 2059. Nell’ articolo del 29 marzo ho fatto uno spoiler: i numeri primi da cercare sono due. (Ho detto anche quali erano. Ora però li terrò nascosti per chi non ha letto il primo articolo e non vuole lo spoiler sulle loro identità xD).
Non è un caso se vi ho proposto un numero (2059) che è il prodotto di due numeri primi.
La sicurezza del cifrario RSA (di cui ho parlato brevemente nell’ articolo del 29 marzo) ruota intorno ad un numero che è il prodotto di due numeri primi molto grandi (anche di 250 cifre!). Fattorizzare quel numero equivale a violare la sicurezza del cifrario xD. (Ancora non posso parlare nel dettaglio dell’ RSA perché devo prima introdurre alcuni concetti di matematica: l’ appuntamento però è solo rimandato di qualche articolo!) Vi cito come esempio un numero di 270 cifre che non è stato ancora fattorizzato e che può essere utilizzato in un cifrario RSA (gli inventori del cifrario RSA hanno chiamato questo numero “RSA-896”):
RSA-896 = 412023436986659543855531365332575948179811699844327982845455626433876445565248426198098870423161841879261420247188869492560931776375033421130982397485150944909106910269861031862704114880866970564902903653658867433731720813104105190864254793282601391257624033946373269391
Dopo aver fatto voli pindarici con numeri di 250 e 270 cifre, torniamo sulla Terra e proviamo a fattorizzare 2059 nel prodotto di due numeri primi. Siccome i numeri da cercare sono due, possiamo fare due considerazioni:
1. Una volta trovato uno dei due numeri, è immediato trovare l’ altro. Per non fare confusione con il linguaggio, chiamiamo il primo numero p e il secondo q. Una volta che avremo trovato p, potremo calcolare q facendo
q = 2059 / p
2. Sicuramente uno dei due numeri è più piccolo della radice quadrata di 2059, ovvero 45 “e un po’” (i numeri dopo la virgola non ci interessano). Per avere conferma di questa cosa, provate a moltiplicare tra loro due numeri che sono più grandi di 45 (come ho detto nell’ articolo del 29 marzo, la moltiplicazione di due numeri è un’ operazione facile, sempre se vi piace la matematica xD). Otterrete sempre un risultato che è più grande di 2059. Ad esempio:
47 x 52 = 2444
Ora che abbiamo fatto tutte le dovute premesse, arriviamo al cuore della videnda:
Come funziona il metodo a forza bruta? Supponiamo che Alice (una ragazza qualsiasi, ma andava bene anche “un ragazzo di nome Bob”) decida di fattorizzare 2059 usando il metodo brute force. Ricordiamo che per trovare i due numeri primi che moltiplicati danno 2059 è sufficiente trovarne uno (perché poi l’ altro si ricava facendo una semplice divisione, vedi la prima delle due considerazioni fatte poco sopra). Ecco come procede Alice:
Quante operazioni deve fare Alice? Alice deve calcolare in tutto 28 divisioni.
Ora che Alice ha trovato uno dei due numeri, come fa a trovare l’ altro? Per calcolare l’ altro numero, Alice deve solamente dividere 2059 per il numero che ha trovato, ovvero 29. Alice però ha già fatto questo calcolo nel 28-esimo passo del metodo brute force (e perché sprecare tempo per cercare un risultato che già si conosce?) Il risultato della divisione è 71, e questo significa che 29 e 71 sono i due numeri primi che cercava Alice!
Giunti a questo punto della storia, sorge spontanea una domanda: ha senso utilizzare il metodo brute force? La risposta è: Si, ma solo quando il numero da fattorizzare è molto piccolo. Un computer ci mette un attimo a calcolare il risultato di un centinaio di operazioni (e se avete un numero di quattro cifre non ve ne servono di più per fattorizzarlo!), ma provate ad usare il metodo brute con un numero molto grande, ad esempio con RSA-896: ci impieghereste una vita anche utilizzando un computer molto potente!
Nel prossimo degli articoli dedicati alla fattorizzazione ci occuperemo di altro metodo, quello di Fermat. Nel frattempo scrivete pure nei commenti se avete dubbi o domande riguardanti il metodo brute force. Buona crittografia! xD
Apri un sito e guadagna con Altervista - Disclaimer - Segnala abuso - Privacy Policy - Personalizza tracciamento pubblicitario