Conteúdo principal
Ciência da Computação
Curso: Ciência da Computação > 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?
© 2023 Khan AcademyTermos de usoPolítica de privacidadeAviso de cookies
Função totiente de Euler
Medição da divisibilidade de um número. Versão original criada por Brit Cruise.
Quer participar da conversa?
- Para que serve a função de Euler?(1 voto)
- determinar a funçao de euler ∅(53)(1 voto)
Transcrição de vídeo
RKA4 - Euler continuou a investigar as propriedades dos números, especificamente a distribuição dos números primos. Uma função importante que ele definiu é chamada de "Função Phi". [Φ] Essa função mede a capacidade de quebra de um número. Assim, dado o número, por exemplo "N", ele mostra quantos números inteiros são menores do que, ou iguais a, N. Esses números inteiros não podem compartilhar qualquer fator comum com N. Por exemplo, se quisermos encontrar o Φ8, olharemos para todos os valores de 1 a 8. Então, contamos quantos inteiros não compartilham um fator maior do que 1 com o número 8. Note que 6 não é contado porque compartilha um fator de 2, enquanto 1, 3, 5 e 7 são todos contados porque apenas partilham um fator de 1. Portanto, Φ8 é igual a 4. O interessante é que o cálculo da função de Φ é difícil, exceto em um caso. Olha para esse gráfico. É um gráfico de valores de Φ sobre números inteiros de um a mil. Você nota qualquer padrão previsível? Essa reta de pontos que cruza o gráfico do eixo zero-zero até o eixo mil-mil, marcado em verde, representa todos os números primos. Já que números primos não tem nenhum valor maior que 1, o Φ de qualquer número primo "P" é simplesmente "P menos 1". Outro exemplo: para calcular o Φ7, um número primo, contamos todos os inteiros, exceto 7, uma vez que nenhum deles compartilha um fator com 7. O Φ7 é igual a 6. Então, se você está procurando encontrar Φ21.377, um número primo, você só precisa subtrair 1 para obter a solução 21.376. O Φ de qualquer número primo é fácil de calcular. Isso leva a um resultado interessante, baseado no fato que a função Φ também é multiplicativa, ou seja, Φ(A vezes B) é igual a ΦA vezes ΦB. Se sabemos que o número N é o produtos de dois números primos, P1 e P2, então ΦN é apenas o valor de Φ para cada número primo multiplicado um pelo outro, ou P1 menos 1 vezes P2 menos 1.