Teste de primalidade de Fermat

RKA 3 - 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 virgem que

fizemos uma demonstração visual do

Teorema de Fermat.
Vimos uma regra

bastante interessante que era dado um

número primo "p" e eu inteiro a

que é menor do que "p".
Sabemos que P dividir a

elevado up - a.
E escrevemos isso como

a elevado up mod P geral se você encontra

o teorema desse jeito e como a equipe

não tem um fator comum.
Já que "p" é primo,

podemos cancelar estes elementos.

E, às vezes, você vai encontrar escrito

a elevado a p - 1 = 1 mod p.

E lembre-se 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 escolhido.

E aí, perguntamos o maior

divisor comum entre "a" e "p" é 1.

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 a chave

a elevado a p menos um modo de p = um

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.

E 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

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.

O 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 o novo "a"
e torcemos para

não encontrar um enganador.

Agora, 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 reflexões,
a probabilidade de que

nenhuma testemunha seja

encontrada com um número composto é no máximo 1.

E vai bater 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 o

site 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 encontra?

Eu vou deixar aqui como

exercício e pesquisa.
Então, não perca tempo e

tente buscar a resposta.

E eu espero que esta
aula tenha te ajudado e

até a próxima pessoal!