1
00:00:00,056 --> 00:00:08,201
Oltre 2000 anni fa Euclide mostrò che ogni numero è fattorizzabile 
in numeri primi in modo unico, una specie di chiave segreta

2
00:00:08,201 --> 00:00:13,833
La fattorizzazione è un problema difficle

3
00:00:13,956 --> 00:00:21,269
Chiariamo cosa intendiamo per 'facile' e 'difficile' 
introducendo la cosiddetta 'complessità temporale'

4
00:00:21,269 --> 00:00:26,938
Tutti sappiamo fare una moltiplicazione

5
00:00:26,945 --> 00:00:32,886
Se programmiamo la moltiplicazione in un computer, 
lo fa più velocemente di qualsiasi essere umano

6
00:00:32,966 --> 00:00:38,614
Questo è un grafico che mostra il tempo impiegato 
da un computer per moltiplicare due numeri

7
00:00:38,614 --> 00:00:44,162
Ovviamente il tempo per trovare la risposta 
aumenta all'aumentare dei numeri

8
00:00:44,162 --> 00:00:50,127
Notate che il tempo è sempre inferiore al secondo, 
anche con numeri grandi

9
00:00:50,127 --> 00:00:55,613
Si dice che è un'operazione 'facile'. 
Ora confrontatela con la fattorizzazione

10
00:00:55,613 --> 00:01:02,540
Fattorizzare 589 è molto più difficile

11
00:01:02,540 --> 00:01:10,244
Qualunque sia l'approccio, ci vorranno parecchi tentativi 
prima di trovare uno qualsiasi dei divisori di 589

12
00:01:10,244 --> 00:01:16,292
Alfine troverete che la fattorizzazione di 589 è 19x31

13
00:01:16,292 --> 00:01:25,918
E se vi chiedessero di trovare la fattorizzazione di 437.231
probabilmente vi arrendereste e ricorrereste all'aiuto d'un computer

14
00:01:25,944 --> 00:01:34,078
Tutto funziona per numeri piccoli, mentre per numeri 
grandi c'è un effetto "esponenziale"

15
00:01:34,078 --> 00:01:40,744
Il tempo necessario a calcolare la fattorizzazione 
aumenta rapidamente

16
00:01:40,744 --> 00:01:44,243
all'aumentare del numero, in minuti e poi ore

17
00:01:44,243 --> 00:01:49,410
fino a necessitare di centinaia o migliaia d'anni 
per fattorizzare numeri elevatissimi

18
00:01:49,410 --> 00:01:57,202
Diciamo la fattorizzazione di numeri molto grandi è un problema difficile, 
a causa dell'aumentare del tempo necessario a trovare la soluzione

19
00:01:57,202 --> 00:02:01,660
La fattorizzazione è quello che Cock usò per costruire 
la botola

20
00:02:01,660 --> 00:02:09,327
Passo1: immaginiamo che Alice generi in modo casuale un numero primo avente 150 cifre e chiamiamolo P1

21
00:02:09,327 --> 00:02:14,992
Quindi che generi un altro numero primo casuale 
delle medesime dimensioni, P2

22
00:02:14,992 --> 00:02:23,222
E che moltiplichi i due numeri primi ottenendo N, 
contenente oltre 300 cifre

23
00:02:23,222 --> 00:02:29,855
Per la moltiplicazione occorrerà meno d'un secondo, 
si può persino fare nel web browser

24
00:02:29,877 --> 00:02:35,461
Alice quindi prende la fattorizzazione di N, 
P1xP2, e la nasconde

25
00:02:35,461 --> 00:02:42,815
Se desse N a chiunque, questi impiegherebbe anni 
per trovare la soluzione, sia pure con l'aiuto d'un computer

26
00:02:42,831 --> 00:02:50,162
Passo 2: Cocks deve scovare una funzione che dipenda 
dalla conoscenza della fattorizzazione di N

27
00:02:50,162 --> 00:02:55,422
Per questo si rivolse al lavoro del matematico svizzero 
Leonardo Eulero nel 1760.