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!