Há mais de 2 mil anos
Euclides mostrou

que todo número possui
apenas uma fatoração prima,

que pode ser vista como uma chave secreta.

Acontece que a fatoração prima é um 
problema naturalmente complicado.

Deixe-me explicar o que é fácil,

e o que é difícil,

introduzindo a Complexidade de Tempo.

Todos nós já multiplicamos números antes

e cada um tem seu modo
para acelerar o processo.

Se programarmos um computador 
para multiplicar números,

ele pode fazer isso muito mais 
rápido do que um humano.

Aqui está um gráfico que mostra 
o tempo necessário

para um computador multiplicar 
dois números.

E, claro, o tempo necessário 
para encontrar a resposta

aumenta quando os números crescem.

Note que o tempo de cálculo fica 
bem abaixo de 1 segundo

mesmo com números
bem grandes.

Portanto, é fácil de ser feito.

Agora compare isso com a fatoração prima.

Se te pedem para encontrar
a fatoração prima de 589,

você notará que o problema 
parece mais difícil.

Não importa a sua estratégia,

você vai precisar de algumas tentativas
para encontrar um divisor de 589.

Com algum esforço, você perceberá
que 19x31 é a fatoração prima.

Se te pedissem para encontrar
a fatoração prima de 437.231,

você provavelmente desistiria 
e usaria um computador.

Isso funciona bem para números pequenos,

mas se usamos um computador para fatorar
números cada vez maiores,

há um efeito de fuga.

O tempo necessário para realizar 
os cálculos cresce rapidamente,

já que há mais passos envolvidos.

À medida que os números crescem,

o computador leva minutos, e então horas,

e eventualmente, precisará 
de centenas ou milhares de anos

para fatorar números enormes.

Nós, portanto, dizemos que
é um problema difícil,

devido a essa taxa de crescimento
do tempo necessário para resolver .

Então fatoração foi o que Cock usou para 
desenvolver a solução do alçapão.

Passo 1.

Imagine que Alice gera um 
número primo aleatório

com mais de 150 dígitos.

Denote-o por P1.

Então, um segundo número primo
com quase o mesmo número de dígitos.

Denote-o por P2.

Ela então multiplica esses 
dois números primos

para conseguir um número composto N,

que possui mais de 300 dígitos.

Esse passo de multiplicação
levaria menos que 1 segundo.

Nós até conseguimos fazer isso
em um navegador de Internet.

Ela então pega a fatoração de N,
P1 vezes P2, e a esconde.

Agora, se ela der N a qualquer pessoa,

essa pessoa teria que ter um computador
rodando durante anos para ter a solução.

Passo 2.

Cock precisa descobrir uma função que 
depende de conhecer a fatoração de N.

Para isso, ele olha o trabalho de 1760
do matemático suíço Leohnard Euler.

Legendado por [Gabriel Mello Gomes]
Revisado por [Alberto Oliveira]