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]