0:00:00.000,0:00:02.364
Há mais de 2 mil anos[br]Euclides mostrou

0:00:02.364,0:00:06.051
que todo número possui[br]apenas uma fatoração prima,

0:00:06.051,0:00:09.193
que pode ser vista como uma chave secreta.

0:00:09.193,0:00:14.205
Acontece que a fatoração prima é um [br]problema naturalmente complicado.

0:00:14.205,0:00:17.222
Deixe-me explicar o que é fácil,

0:00:17.232,0:00:18.281
e o que é difícil,

0:00:18.281,0:00:21.131
introduzindo a Complexidade de Tempo.

0:00:21.155,0:00:23.308
Todos nós já multiplicamos números antes

0:00:23.318,0:00:27.408
e cada um tem seu modo[br]para acelerar o processo.

0:00:27.427,0:00:30.106
Se programarmos um computador [br]para multiplicar números,

0:00:30.106,0:00:33.348
ele pode fazer isso muito mais [br]rápido do que um humano.

0:00:33.348,0:00:35.788
Aqui está um gráfico que mostra [br]o tempo necessário

0:00:35.788,0:00:39.392
para um computador multiplicar [br]dois números.

0:00:39.392,0:00:42.152
E, claro, o tempo necessário [br]para encontrar a resposta

0:00:42.152,0:00:44.350
aumenta quando os números crescem.

0:00:44.350,0:00:48.280
Note que o tempo de cálculo fica [br]bem abaixo de 1 segundo

0:00:48.280,0:00:50.716
mesmo com números[br]bem grandes.

0:00:50.716,0:00:53.366
Portanto, é fácil de ser feito.

0:00:53.372,0:00:55.841
Agora compare isso com a fatoração prima.

0:00:55.841,0:00:59.711
Se te pedem para encontrar[br]a fatoração prima de 589,

0:00:59.714,0:01:02.974
você notará que o problema [br]parece mais difícil.

0:01:02.976,0:01:04.996
Não importa a sua estratégia,

0:01:05.002,0:01:09.997
você vai precisar de algumas tentativas[br]para encontrar um divisor de 589.

0:01:10.010,0:01:16.270
Com algum esforço, você perceberá[br]que 19x31 é a fatoração prima.

0:01:16.296,0:01:22.736
Se te pedissem para encontrar[br]a fatoração prima de 437.231,

0:01:22.748,0:01:26.102
você provavelmente desistiria [br]e usaria um computador.

0:01:26.102,0:01:28.614
Isso funciona bem para números pequenos,

0:01:28.614,0:01:32.889
mas se usamos um computador para fatorar[br]números cada vez maiores,

0:01:32.889,0:01:35.068
há um efeito de fuga.

0:01:35.068,0:01:38.825
O tempo necessário para realizar [br]os cálculos cresce rapidamente,

0:01:38.825,0:01:40.798
já que há mais passos envolvidos.

0:01:40.798,0:01:42.333
À medida que os números crescem,

0:01:42.333,0:01:44.504
o computador leva minutos, e então horas,

0:01:44.504,0:01:47.904
e eventualmente, precisará [br]de centenas ou milhares de anos

0:01:47.904,0:01:49.824
para fatorar números enormes.

0:01:49.832,0:01:53.080
Nós, portanto, dizemos que[br]é um problema difícil,

0:01:53.080,0:01:56.844
devido a essa taxa de crescimento[br]do tempo necessário para resolver .

0:01:56.854,0:02:01.950
Então fatoração foi o que Cock usou para [br]desenvolver a solução do alçapão.

0:02:01.950,0:02:03.367
Passo 1.[br]

0:02:03.367,0:02:06.175
Imagine que Alice gera um [br]número primo aleatório

0:02:06.175,0:02:08.065
com mais de 150 dígitos.

0:02:08.071,0:02:09.461
Denote-o por P1.

0:02:09.469,0:02:14.163
Então, um segundo número primo[br]com quase o mesmo número de dígitos.

0:02:14.163,0:02:15.164
Denote-o por P2.

0:02:15.164,0:02:18.379
Ela então multiplica esses [br]dois números primos

0:02:18.379,0:02:20.533
para conseguir um número composto N,

0:02:20.533,0:02:23.313
que possui mais de 300 dígitos.

0:02:23.323,0:02:26.699
Esse passo de multiplicação[br]levaria menos que 1 segundo.

0:02:26.699,0:02:30.039
Nós até conseguimos fazer isso[br]em um navegador de Internet.

0:02:30.039,0:02:35.300
Ela então pega a fatoração de N,[br]P1 vezes P2, e a esconde.

0:02:35.317,0:02:38.582
Agora, se ela der N a qualquer pessoa,

0:02:38.582,0:02:42.785
essa pessoa teria que ter um computador[br]rodando durante anos para ter a solução.

0:02:42.795,0:02:43.985
Passo 2.[br]

0:02:43.993,0:02:49.863
Cock precisa descobrir uma função que [br]depende de conhecer a fatoração de N.

0:02:49.870,0:02:56.290
Para isso, ele olha o trabalho de 1760[br]do matemático suíço Leohnard Euler.

0:02:56.290,0:02:57.000
Legendado por [Gabriel Mello Gomes][br]Revisado por [Alberto Oliveira]