1
00:00:00,000 --> 00:00:02,364
Há mais de 2 mil anos
Euclides mostrou

2
00:00:02,364 --> 00:00:06,051
que todo número possui
apenas uma fatoração prima,

3
00:00:06,051 --> 00:00:09,193
que pode ser vista como uma chave secreta.

4
00:00:09,193 --> 00:00:14,205
Acontece que a fatoração prima é um 
problema naturalmente complicado.

5
00:00:14,205 --> 00:00:17,222
Deixe-me explicar o que é fácil,

6
00:00:17,232 --> 00:00:18,281
e o que é difícil,

7
00:00:18,281 --> 00:00:21,131
introduzindo a Complexidade de Tempo.

8
00:00:21,155 --> 00:00:23,308
Todos nós já multiplicamos números antes

9
00:00:23,318 --> 00:00:27,408
e cada um tem seu modo
para acelerar o processo.

10
00:00:27,427 --> 00:00:30,106
Se programarmos um computador 
para multiplicar números,

11
00:00:30,106 --> 00:00:33,348
ele pode fazer isso muito mais 
rápido do que um humano.

12
00:00:33,348 --> 00:00:35,788
Aqui está um gráfico que mostra 
o tempo necessário

13
00:00:35,788 --> 00:00:39,392
para um computador multiplicar 
dois números.

14
00:00:39,392 --> 00:00:42,152
E, claro, o tempo necessário 
para encontrar a resposta

15
00:00:42,152 --> 00:00:44,350
aumenta quando os números crescem.

16
00:00:44,350 --> 00:00:48,280
Note que o tempo de cálculo fica 
bem abaixo de 1 segundo

17
00:00:48,280 --> 00:00:50,716
mesmo com números
bem grandes.

18
00:00:50,716 --> 00:00:53,366
Portanto, é fácil de ser feito.

19
00:00:53,372 --> 00:00:55,841
Agora compare isso com a fatoração prima.

20
00:00:55,841 --> 00:00:59,711
Se te pedem para encontrar
a fatoração prima de 589,

21
00:00:59,714 --> 00:01:02,974
você notará que o problema 
parece mais difícil.

22
00:01:02,976 --> 00:01:04,996
Não importa a sua estratégia,

23
00:01:05,002 --> 00:01:09,997
você vai precisar de algumas tentativas
para encontrar um divisor de 589.

24
00:01:10,010 --> 00:01:16,270
Com algum esforço, você perceberá
que 19x31 é a fatoração prima.

25
00:01:16,296 --> 00:01:22,736
Se te pedissem para encontrar
a fatoração prima de 437.231,

26
00:01:22,748 --> 00:01:26,102
você provavelmente desistiria 
e usaria um computador.

27
00:01:26,102 --> 00:01:28,614
Isso funciona bem para números pequenos,

28
00:01:28,614 --> 00:01:32,889
mas se usamos um computador para fatorar
números cada vez maiores,

29
00:01:32,889 --> 00:01:35,068
há um efeito de fuga.

30
00:01:35,068 --> 00:01:38,825
O tempo necessário para realizar 
os cálculos cresce rapidamente,

31
00:01:38,825 --> 00:01:40,798
já que há mais passos envolvidos.

32
00:01:40,798 --> 00:01:42,333
À medida que os números crescem,

33
00:01:42,333 --> 00:01:44,504
o computador leva minutos, e então horas,

34
00:01:44,504 --> 00:01:47,904
e eventualmente, precisará 
de centenas ou milhares de anos

35
00:01:47,904 --> 00:01:49,824
para fatorar números enormes.

36
00:01:49,832 --> 00:01:53,080
Nós, portanto, dizemos que
é um problema difícil,

37
00:01:53,080 --> 00:01:56,844
devido a essa taxa de crescimento
do tempo necessário para resolver .

38
00:01:56,854 --> 00:02:01,950
Então fatoração foi o que Cock usou para 
desenvolver a solução do alçapão.

39
00:02:01,950 --> 00:02:03,367
Passo 1.


40
00:02:03,367 --> 00:02:06,175
Imagine que Alice gera um 
número primo aleatório

41
00:02:06,175 --> 00:02:08,065
com mais de 150 dígitos.

42
00:02:08,071 --> 00:02:09,461
Denote-o por P1.

43
00:02:09,469 --> 00:02:14,163
Então, um segundo número primo
com quase o mesmo número de dígitos.

44
00:02:14,163 --> 00:02:15,164
Denote-o por P2.

45
00:02:15,164 --> 00:02:18,379
Ela então multiplica esses 
dois números primos

46
00:02:18,379 --> 00:02:20,533
para conseguir um número composto N,

47
00:02:20,533 --> 00:02:23,313
que possui mais de 300 dígitos.

48
00:02:23,323 --> 00:02:26,699
Esse passo de multiplicação
levaria menos que 1 segundo.

49
00:02:26,699 --> 00:02:30,039
Nós até conseguimos fazer isso
em um navegador de Internet.

50
00:02:30,039 --> 00:02:35,300
Ela então pega a fatoração de N,
P1 vezes P2, e a esconde.

51
00:02:35,317 --> 00:02:38,582
Agora, se ela der N a qualquer pessoa,

52
00:02:38,582 --> 00:02:42,785
essa pessoa teria que ter um computador
rodando durante anos para ter a solução.

53
00:02:42,795 --> 00:02:43,985
Passo 2.


54
00:02:43,993 --> 00:02:49,863
Cock precisa descobrir uma função que 
depende de conhecer a fatoração de N.

55
00:02:49,870 --> 00:02:56,290
Para isso, ele olha o trabalho de 1760
do matemático suíço Leohnard Euler.

56
00:02:56,290 --> 00:02:57,000
Legendado por [Gabriel Mello Gomes]
Revisado por [Alberto Oliveira]