-
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!