-
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]
