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 enfermar 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 esses 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 Ai p é um agora

podemos ver uma demonstração de como

isso funciona é 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 ar

que você escolha mas Se colocarmos um

número composto para o p podemos ver que

normalmente o resultado não vai ser um a

maioria das vezes vai ser diferente de

um O resultado vai ser composto Isso é

uma prova de que o pé que escolhemos não

pode ser primo Essa é essência do teste

e antes de prosseguir e 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 IP é um senão ou

seja se o MDC entre a equipe é maior do

que um 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

senão vamos ter que p é composto E

paramos por aqui caso contrário se a

equação for igual a 1 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 firmar 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 Esse

é um exemplo do que chamamos de falso

primo é um número composto mas existem

alguns as que escolhemos que resultam em

um e eles são chamados de enganadores

isso porque eles nos fazem pensar que a

resposta é um número primo

o que mudando o ar 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 e agora nós

conseguimos ver que esses 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 nesse grupo

podem ser enganadores então desde que o

ar 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 um / 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 e note

que no pior caso que sabemos que é

quando temos um algoritmo com esse primo

a máquina vai ter um trabalho muito

grande para gerar o teste de enfermar é

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 fé eu 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 nesse 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 tem te buscar a resposta e eu

espero que essa aula tenha te ajudado e

até a próxima pessoal