Oltre 2000 anni fa Euclide mostrò che ogni numero è fattorizzabile in numeri primi in modo unico, una specie di chiave segreta
La fattorizzazione è un problema difficle
Chiariamo cosa intendiamo per 'facile' e 'difficile' introducendo la cosiddetta 'complessità temporale'
Tutti sappiamo fare una moltiplicazione
Se programmiamo la moltiplicazione in un computer, lo fa più velocemente di qualsiasi essere umano
Questo è un grafico che mostra il tempo impiegato da un computer per moltiplicare due numeri
Ovviamente il tempo per trovare la risposta aumenta all'aumentare dei numeri
Notate che il tempo è sempre inferiore al secondo, anche con numeri grandi
Si dice che è un'operazione 'facile'. Ora confrontatela con la fattorizzazione
Fattorizzare 589 è molto più difficile
Qualunque sia l'approccio, ci vorranno parecchi tentativi prima di trovare uno qualsiasi dei divisori di 589
Alfine troverete che la fattorizzazione di 589 è 19x31
E se vi chiedessero di trovare la fattorizzazione di 437.231 probabilmente vi arrendereste e ricorrereste all'aiuto d'un computer
Tutto funziona per numeri piccoli, mentre per numeri grandi c'è un effetto "esponenziale"
Il tempo necessario a calcolare la fattorizzazione aumenta rapidamente
all'aumentare del numero, in minuti e poi ore
fino a necessitare di centinaia o migliaia d'anni per fattorizzare numeri elevatissimi
Diciamo la fattorizzazione di numeri molto grandi è un problema difficile, a causa dell'aumentare del tempo necessario a trovare la soluzione
La fattorizzazione è quello che Cock usò per costruire la botola
Passo1: immaginiamo che Alice generi in modo casuale un numero primo avente 150 cifre e chiamiamolo P1
Quindi che generi un altro numero primo casuale delle medesime dimensioni, P2
E che moltiplichi i due numeri primi ottenendo N, contenente oltre 300 cifre
Per la moltiplicazione occorrerà meno d'un secondo, si può persino fare nel web browser
Alice quindi prende la fattorizzazione di N, P1xP2, e la nasconde
Se desse N a chiunque, questi impiegherebbe anni per trovare la soluzione, sia pure con l'aiuto d'un computer
Passo 2: Cocks deve scovare una funzione che dipenda dalla conoscenza della fattorizzazione di N
Per questo si rivolse al lavoro del matematico svizzero Leonardo Eulero nel 1760.