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