Conteúdo principal
Curso: Computer science theory > Unidade 2
Lição 4: Criptografia moderna- Teorema fundamental da aritmética
- Criptografia de chave pública: o que é isso?
- O problema do logarítmo discreto
- Troca de chaves Diffie-Hellman
- Criptografia RSA: etapa 1
- Criptografia RSA: etapa 2
- Criptografia RSA: etapa 3
- Complexidade do Tempo (Exploração)
- Função totiente de Euler
- Exploração da Função Totiente de Euler
- Criptografia RSA: etapa 4
- O que devemos aprender em seguida?
© 2024 Khan AcademyTermos de usoPolítica de privacidadeAviso de cookies
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?
- como posso assistir o video com audio em portugues ou legendas(1 voto)
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.