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.