Teste de primalidade de Fermat

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!