-
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 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"
-
elevado a p - a.
E escrevemos isso como,
-
"a" elevado a "p mod p.
Geralmente, você encontra
-
o teorema deste jeito.
E como "a" e "p"
-
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 "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 a chave.
-
"a" elevado a p - 1 mod p é igual a 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 elevado a "t".
-
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.
-
E eu espero que esta
aula tenha te ajudado e
-
até a próxima pessoal!