-
Precisamos de um procedimento numérico que seja fácil em uma direção,
-
e difícil na outra.
-
Isso nos traz à aritmética modular, também conhecida como aritmética do relógio.
-
Por exemplo, para encontrar 46 mod 12, pegamos uma corda de 46 unidades de comprimento
-
e a enrolamos ao redor de um relógio de 12 unidades que é chamado de modulador,
-
e onde a corda acaba é a solução.
-
Então dizemos que 46 mod 12 é congruente a 10.
-
Fácil. Agora para fazer isso funcionar, usamos um modulador primo, como 17.
-
Então achamos uma raiz primitiva de 17, nesse caso, 3.
-
Que tem essa importante propriedade que quando elevado a expoentes diferentes,
-
a solução é distribuída uniformemente ao redor do relógio.
-
3 é conhecido como o gerador. Se elevarmos 3 a qualquer expoente x,
-
então a solução é igualmente provável de ser qualquer número entre 0 e 17.
-
Agora, o procedimento inverso é difícil.
-
Digamos que, dado 12, ache o expoente a que 3 precisa ser elevado.
-
Isso é chamado de problema do Logaritmo Discreto.
-
E agora temos nossa função de uma só direção.
-
Fácil de fazer, difícil de reverter.
-
Dado 12, teríamos que tentar achar com tentativa e erro para encontrar o expoente.
-
Quão difícil é isso?
-
Bem, com números pequenos é facil, mas se usarmos um modulador primo que tem centenas de dígitos,
-
fica imprático resolver.
-
Mesmo se você tivesse acesso a todo o poder computacional na terra, poderia levar milhares de anos
-
para testar todas as possibilidades.
-
Então a força de uma função de uma direção é baseada no tempo necessário para revertê-la.
