-
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.
