Return to Video

Teste de primalidade de Fermat

  • 0:00 - 0:02
    RKA3JV - E aí, pessoal!
    Tudo bem?
  • 0:02 - 0:06
    Nesta aula, vamos fazer o teste
    de primalidade de Fermat.
  • 0:06 - 0:11
    Para isso, vamos determinar uma série
    de instruções que possam provar
  • 0:11 - 0:14
    se um número inteiro de entrada é composto
  • 0:14 - 0:17
    ou primo com alto grau de precisão.
  • 0:17 - 0:21
    Claro, seria mais fácil calcular isso
    em qualquer máquina.
  • 0:21 - 0:24
    E mesmo que um número
    de entrada aumente,
  • 0:24 - 0:27
    isso ainda deveria ser mais rápido,
    correto?
  • 0:27 - 0:31
    Até agora nós aprendemos que
    precisamos reconhecer um padrão
  • 0:31 - 0:34
    que todos os números primos têm,
  • 0:34 - 0:36
    e que alguns compostos não.
  • 0:36 - 0:40
    E no vídeo em que fizemos uma
    demonstração visual do Teorema de Fermat,
  • 0:40 - 0:43
    vimos uma regra bastante interessante
  • 0:43 - 0:46
    que era, dado um número primo "p"
  • 0:46 - 0:49
    e o inteiro "a", que é menor do que "p",
  • 0:49 - 0:54
    sabemos que "p" divide "aᵖ - a".
  • 0:54 - 0:59
    E escrevemos isso como, "aᵖ = a mod p".
  • 0:59 - 1:03
    Geralmente, você encontra
    o teorema deste jeito.
  • 1:03 - 1:07
    E como "a" e "p" não têm um fator comum,
    já que "p" é primo,
  • 1:07 - 1:09
    podemos cancelar estes elementos.
  • 1:09 - 1:18
    E, às vezes, você vai encontrar escrito
    "aᵖ⁻¹ = 1 mod p".
  • 1:18 - 1:20
    E lembre-se de que só podemos fazer isso,
  • 1:20 - 1:24
    porque o maior divisor comum
    entre "a" e "p" é 1.
  • 1:24 - 1:28
    Agora, podemos ver uma demonstração
    de como isso funciona
  • 1:28 - 1:30
    para entender melhor o processo.
  • 1:30 - 1:34
    Note que se você colocar um
    número primo para o "p",
  • 1:34 - 1:37
    o resultado vai ser sempre igual a 1,
  • 1:37 - 1:39
    não importa o "a" que você escolha.
  • 1:39 - 1:42
    Mas, se colocarmos um número
    composto para o "p",
  • 1:42 - 1:46
    podemos ver que normalmente
    o resultado não vai ser 1.
  • 1:46 - 1:50
    A maioria das vezes
    vai ser diferente de 1.
  • 1:50 - 1:52
    O resultado vai ser composto.
  • 1:52 - 1:56
    Isto é uma prova de que o "p"
    que escolhemos não pode ser primo.
  • 1:56 - 1:58
    Essa é essência do teste.
  • 1:58 - 2:00
    E antes de prosseguir,
  • 2:00 - 2:03
    vamos construir uma estrutura
    aqui para ele
  • 2:03 - 2:06
    utilizando o padrão
    que eu mostrei.
  • 2:06 - 2:11
    Primeiro, nós temos uma entrada
    que vai ser um número inteiro "p".
  • 2:11 - 2:15
    Depois, geramos um número
    inteiro aleatório
  • 2:15 - 2:18
    que é menor do que o "p" escolhido.
  • 2:18 - 2:19
    E aí, perguntamos:
  • 2:19 - 2:23
    o maior divisor comum
    entre "a" e "p" é 1?
  • 2:23 - 2:28
    Se não, ou seja, se o MDC entre "a" e "p"
    é maior do que 1,
  • 2:28 - 2:30
    eles vão compartilhar de
    um fator comum, correto?
  • 2:30 - 2:34
    E, com isso, o "p" vai ser
    um número composto.
  • 2:34 - 2:37
    Com isso, o resultado vai ser
    um número composto.
  • 2:37 - 2:38
    Agora, se tivermos.
  • 2:38 - 2:41
    Sim, podemos responder à pergunta-chave.
  • 2:41 - 2:46
    "aᵖ⁻¹ mod p = 1?
  • 2:46 - 2:49
    Se não, vamos ter que "p" é composto,
  • 2:49 - 2:50
    e paramos por aqui.
  • 2:50 - 2:53
    Caso contrário, se a equação
    for igual a 1,
  • 2:53 - 2:56
    "p" deve ser primo, correto?
  • 2:56 - 2:58
    E eu codifiquei essa série
    de instruções aqui
  • 2:58 - 3:00
    e vamos ver o que acontece?
  • 3:00 - 3:03
    Do lado esquerdo,
    nós temos o teste de Fermat.
  • 3:03 - 3:08
    Do lado direito, nós temos
    o teste de divisão experimental.
  • 3:08 - 3:11
    Veja que parece que sempre vai dar certo.
  • 3:11 - 3:15
    Só de olhar você consegue ver que
    os valores são sempre os mesmos,
  • 3:15 - 3:19
    não importa o valor que eu
    modifique no meu algoritmo.
  • 3:19 - 3:22
    Porém, eu encontro um problema aqui.
  • 3:22 - 3:25
    Eu coloquei o número 511
  • 3:25 - 3:28
    e o Teorema de Fermat está
    dizendo que é primo.
  • 3:28 - 3:32
    Já o teste da divisão experimental,
    diz que é composto.
  • 3:32 - 3:34
    O que será que está acontecendo?
  • 3:34 - 3:38
    O 511, de fato, não é um número primo.
  • 3:38 - 3:41
    E vamos voltar aqui na nossa equação
    e ver o que aconteceu.
  • 3:41 - 3:46
    Este é um exemplo do que
    chamamos de falso primo.
  • 3:46 - 3:49
    É um número composto,
    mas existem alguns "a"
  • 3:49 - 3:51
    que escolhemos que resultam em 1.
  • 3:51 - 3:54
    E eles são chamados de enganadores.
  • 3:54 - 3:59
    Isso porque eles nos fazem pensar
    que a resposta é um número primo.
  • 3:59 - 4:01
    E note que mudando o "a",
  • 4:01 - 4:04
    encontramos muitos
    números compostos
  • 4:04 - 4:06
    que eu vou chamar
    de testemunhas.
  • 4:06 - 4:08
    Eles não são enganadores.
  • 4:08 - 4:14
    Agora, podemos utilizar a mesma lógica
    que usamos no teste de divisibilidade,
  • 4:14 - 4:16
    onde geramos um novo "a"
  • 4:16 - 4:20
    e torcemos para não encontrar
    um enganador.
  • 4:20 - 4:24
    Agora, nós conseguimos ver que
    estes enganadores
  • 4:24 - 4:28
    dividem o número total do grupo
    que estamos selecionando.
  • 4:28 - 4:33
    Isso significa que no máximo
    metade das escolhas
  • 4:33 - 4:36
    ou metade dos elementos
    selecionados neste grupo,
  • 4:36 - 4:39
    podem ser enganadores.
  • 4:39 - 4:43
    Então, desde que o "a"
    seja encontrado aleatoriamente,
  • 4:43 - 4:45
    a chance de encontrar uma testemunha,
  • 4:45 - 4:48
    que é o que queremos,
    é pelo menos a metade.
  • 4:48 - 4:51
    E depois de ter repetições,
  • 4:51 - 4:55
    a probabilidade de que nenhuma
    testemunha seja encontrada
  • 4:55 - 5:01
    com um número composto é
    no máximo 1/2ᵗ.
  • 5:01 - 5:04
    Depois de 20 tentativas,
    por exemplo,
  • 5:04 - 5:08
    a probabilidade de sair um
    número primo erroneamente
  • 5:08 - 5:11
    é de uma em um milhão,
    aproximadamente.
  • 5:11 - 5:15
    É aquele caso onde continuamos
    com uma má sorte
  • 5:15 - 5:18
    em gerar os "a" aleatórios
  • 5:18 - 5:21
    e toda vez encontramos um enganador.
  • 5:21 - 5:24
    E agora sim podemos ver
    nosso teste em ação.
  • 5:24 - 5:27
    Com o maior número de tentativas,
  • 5:27 - 5:30
    parece que o teste está funcionando
    perfeitamente, correto?
  • 5:30 - 5:33
    Note que, no pior caso,
  • 5:33 - 5:37
    que sabemos que é quando temos
    um algoritmo com este primo,
  • 5:37 - 5:41
    a máquina vai ter um trabalho muito
    grande para gerar o teste de Fermat.
  • 5:41 - 5:45
    É muito mais eficiente que
    a divisão experimental.
  • 5:45 - 5:46
    Principalmente,
  • 5:46 - 5:50
    porque o número de passos
    não aumenta com a entrada.
  • 5:50 - 5:51
    Por exemplo,
  • 5:51 - 5:55
    graficamente relacionando
    o tempo e o tamanho da entrada,
  • 5:55 - 5:57
    vai ser algo, mais ou menos, assim.
  • 5:57 - 6:02
    Basicamente, no teste de Fermat
    nunca temos que nos preocupar
  • 6:02 - 6:06
    com o algoritmo rodando milhões
    e milhões de vezes
  • 6:06 - 6:09
    de repetições como fizemos antes.
  • 6:09 - 6:14
    Então, o que eu quero dizer é que isso
    nada mais é do que matemática aplicada.
  • 6:14 - 6:18
    Ou seja, pegamos um padrão
    que alguém descobriu
  • 6:18 - 6:22
    e colocamos uma grande quantidade
    de repetições no computador,
  • 6:22 - 6:24
    isso através de programação.
  • 6:24 - 6:26
    Mas, neste sistema aqui,
  • 6:26 - 6:28
    tem uma pequena falha.
  • 6:28 - 6:30
    Será que você consegue encontrar?
  • 6:30 - 6:32
    Eu vou deixar aqui como
    exercício e pesquisa.
  • 6:32 - 6:36
    Então, não perca tempo
    e tente buscar a resposta.
  • 6:36 - 6:39
    Eu espero que esta aula
    tenha lhes ajudado
  • 6:39 - 6:41
    e até a próxima, pessoal!
Titel:
Teste de primalidade de Fermat
Beschreibung:

more » « less
Video Language:
Portuguese
Team:
Khan Academy
Projekt:
Accessibility Brazil
Duration:
06:47

Untertitel in Portuguese

Revisionen Compare revisions