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]