If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

O problema do logarítmo discreto

Um bloqueio matemático usando aritmética modular. Versão original criada por Brit Cruise.

Quer participar da conversa?

Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.

Transcrição de vídeo

RKA4JL - Nós precisamos de um procedimento numérico, o qual é fácil em uma direção e difícil na outra. Isso nos leva à aritmética modular, também conhecida como relógio aritmético. Por exemplo, para achar 46 módulo 12 poderíamos pegar uma corda com o comprimento de 46 unidades e enrolar em volta de um relógio de 12 unidades, o qual é chamado de módulo. E onde a corda acaba é a solução. Então, nós dizemos que 46 módulo 12 é congruente a 10. Fácil. Agora, para fazer com que isso funcione, nós usamos um módulo primo, como o 17. Então, nós encontramos a raiz primitiva de 17, neste caso, 3, a qual possui essa propriedade importante que, quando elevada a diferentes expoentes, a solução se distribui uniformemente pelo relógio. 3 é conhecido como um gerador. Se elevarmos 3 a qualquer expoente "X", a solução será igualmente provável que seja qualquer inteiro entre zero e 17. Agora, o procedimento reverso é difícil. Por exemplo, dado 12, encontre o expoente necessário para 3. Isso se chama "o problema do logaritmo discreto". E agora, nós possuímos nossa função de via única: fácil de executar, porém difícil de reverter. Dado 12, nós teremos que recorrer à tentativa e erro para encontrar um expoente certo. O quão difícil é isso? Com números pequenos, isso é fácil. Porém, se usarmos um módulo primo, que são centenas de dígitos de comprimento, isso se tornaria impraticável de ser solucionado. Mesmo que você possua acesso a todos os poderes computacionais da Terra, poderia levar centenas de anos para rodar todas as possibilidades. Assim, a força de uma função de sentido único é baseada no tempo necessário para revertê-la.