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