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!