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
Teorema fundamental da aritmética
Realização independente do ponto de vista de um antepassado. Versão original criada por Brit Cruise.
Quer participar da conversa?
- Isso é demais!! Por isso que amo ciência da computação e matemática!(5 votos)
- incrível, matemática é foda. Ainda mais foda quando narrada pelo dublador do Bear Grylls(3 votos)
- goku dando aula de criptografia? Adorei!!(2 votos)
- Sensacional! Nunca pensei que os numeros primos pudessem ser usados dessa forma.
Vivendo e aprendendo. :D(2 votos) - muito interessante, quero ir ate o fim...great notes!(2 votos)
Transcrição de vídeo
RKA-MP - Imagine que estamos vivendo em tempos
pré-históricos. Considere o seguinte: Como a gente tinha ideia do tempo sem um relógio? Todos os relógios são baseados em algum padrão repetitivo que divide o tempo integral em segmentos iguais. Para achar esses padrões repetitivos,
olhamos para o céu. O Sol nascendo e descendo todos os dias é o mais óbvio. Entretanto, para acompanhar períodos de tempo mais longos, procuramos ciclos mais longos. Para isso, olhamos para a Lua que, gradualmente, cresce e diminui ao longo de vários dias. Quando contamos o número de dias entre luas cheias, chegamos ao número 29. Esta é a origem de um mês. Mas, se tentarmos dividir 29 em pedaços iguais, a gente chega em um problema. É impossível! A única forma de dividir 29 em partes iguais,
é dividir em unidades singulares. 29 é um número primo. Pense nisso como inquebrável. Se um número pode ser quebrado em pedaços iguais maiores do que 1, chamamos de um número composto. Agora, se formos curiosos, podemos pensar quantos números primos há e o quão grande eles ficam. Vamos começar dividindo todos os números em duas categorias. Vamos listar todos os primos na esquerda e os compostos na direita. Inicialmente, parece que eles dançam para a frente para trás, não há padrão óbvio aqui. Então, vamos usar uma técnica moderna para ver uma figura maior. O truque é usar a Espiral de Ulam. Primeiro, listamos todos os possíveis números em ordem, em uma espiral crescente. Depois, colorimos todos os números primos de azul. E, depois, diminuímos o zoom para ver
milhões de números. Este é o padrão dos primos,
que segue assim eternamente. Incrivelmente, a estrutura completa desse padrão ainda não foi resolvida. Estamos em uma coisa legal. Então, vamos acelerar para ao redor de 300 a.C., na Grécia antiga. Um filósofo, conhecido como Euclides de Alexandria, dizia que todos os números poderiam ser divididos em duas categorias separadas. Ele começou percebendo que qualquer número pode ser dividido uma e outra vez até você chegar a um grupo dos menores números iguais. E, por definição, estes menores números são sempre números primos. Então, ele sabia que todos os números são, de alguma forma, construídos a partir de primos menores. Para ser claro, imagine o mundo com todos os números, e ignore os primos. Agora, pegue qualquer número composto e divida.
E sempre sobrarão números primos. Euclides sabia que cada número poderia ser expresso usando um grupo de primos menores. Pense neles como blocos de construção. Não importa que número você escolha, ele sempre pode ser construído com primos menores. Esta é a raiz da descoberta conhecida como
o teorema fundamental da Aritmética. Como segue, pegue qualquer número, como o 30, e ache todos os números primos que o dividem igualmente. Isso é conhecido como fatoração. Isso vai nos dar os fatores primos.
Neste caso, 2, 3 e 5 são fatores primos de 30. Euclides percebeu que você poderia multiplicar esses fatores primos um número específico de vezes para construir um número original. Nesse caso, você pode simplesmente multiplicar cada fator uma vez para chegar a 30. 2 vezes 3, vezes 5 é a fatoração prima de 30. Pense nisso como uma chave especial, ou uma combinação. Não há outra forma de construir 30 usando algum outro grupo de números primos multiplicados em conjunto. Então, cada número possível tem uma, e só uma, fatoração de números primos. Uma forma análoga é imaginar cada número como uma fechadura diferente, a única chave para cada fechadura seria esta fatoração de números primos. Nenhuma fechadura compartilha uma chave com outra, nenhum número compartilha uma fatoração de números primos com outro.