WEBVTT

00:00:00.000 --> 00:00:01.769
RKA3JV - E aí, pessoal! 
Tudo bem?

00:00:01.769 --> 00:00:06.359
Nesta aula, vamos fazer o teste 
de primalidade de Fermat.

00:00:06.359 --> 00:00:11.211
Para isso, vamos determinar uma série 
de instruções que possam provar

00:00:11.211 --> 00:00:13.987
se um número inteiro de entrada é composto

00:00:13.987 --> 00:00:16.830
ou primo com alto grau de precisão.

00:00:16.830 --> 00:00:21.003
Claro, seria mais fácil calcular isso 
em qualquer máquina.

00:00:21.003 --> 00:00:23.842
E mesmo que um número 
de entrada aumente,

00:00:23.842 --> 00:00:26.635
isso ainda deveria ser mais rápido, 
correto?

00:00:26.635 --> 00:00:31.409
Até agora nós aprendemos que 
precisamos reconhecer um padrão

00:00:31.409 --> 00:00:33.833
que todos os números primos têm,

00:00:33.833 --> 00:00:35.722
e que alguns compostos não.

00:00:35.722 --> 00:00:40.449
E no vídeo em que fizemos uma 
demonstração visual do Teorema de Fermat,

00:00:40.449 --> 00:00:43.009
vimos uma regra bastante interessante

00:00:43.009 --> 00:00:45.607
que era, dado um número primo "p"

00:00:45.607 --> 00:00:48.505
e o inteiro "a", que é menor do que "p",

00:00:48.505 --> 00:00:53.602
sabemos que "p" divide "aᵖ - a".

00:00:53.602 --> 00:00:58.827
E escrevemos isso como, "aᵖ = a mod p".

00:00:58.827 --> 00:01:02.544
Geralmente, você encontra 
o teorema deste jeito.

00:01:02.544 --> 00:01:06.940
E como "a" e "p" não têm um fator comum, 
já que "p" é primo,

00:01:06.940 --> 00:01:09.408
podemos cancelar estes elementos.

00:01:09.408 --> 00:01:17.659
E, às vezes, você vai encontrar escrito 
"aᵖ⁻¹ = 1 mod p".

00:01:17.659 --> 00:01:20.064
E lembre-se de que só podemos fazer isso,

00:01:20.064 --> 00:01:23.910
porque o maior divisor comum 
entre "a" e "p" é 1.

00:01:23.910 --> 00:01:27.971
Agora, podemos ver uma demonstração 
de como isso funciona

00:01:27.971 --> 00:01:30.010
para entender melhor o processo.

00:01:30.010 --> 00:01:34.149
Note que se você colocar um 
número primo para o "p",

00:01:34.149 --> 00:01:36.939
o resultado vai ser sempre igual a 1,

00:01:36.939 --> 00:01:39.104
não importa o "a" que você escolha.

00:01:39.104 --> 00:01:42.389
Mas, se colocarmos um número 
composto para o "p",

00:01:42.389 --> 00:01:46.238
podemos ver que normalmente 
o resultado não vai ser 1.

00:01:46.238 --> 00:01:49.540
A maioria das vezes 
vai ser diferente de 1.

00:01:49.540 --> 00:01:51.789
O resultado vai ser composto.

00:01:51.789 --> 00:01:55.918
Isto é uma prova de que o "p"
que escolhemos não pode ser primo.

00:01:55.918 --> 00:01:58.139
Essa é essência do teste.

00:01:58.139 --> 00:01:59.954
E antes de prosseguir,

00:01:59.954 --> 00:02:03.447
vamos construir uma estrutura 
aqui para ele

00:02:03.447 --> 00:02:06.133
utilizando o padrão 
que eu mostrei.

00:02:06.133 --> 00:02:11.276
Primeiro, nós temos uma entrada 
que vai ser um número inteiro "p".

00:02:11.276 --> 00:02:15.111
Depois, geramos um número 
inteiro aleatório

00:02:15.111 --> 00:02:17.679
que é menor do que o "p" escolhido.

00:02:17.679 --> 00:02:19.159
E aí, perguntamos:

00:02:19.159 --> 00:02:22.851
o maior divisor comum 
entre "a" e "p" é 1?

00:02:22.851 --> 00:02:27.610
Se não, ou seja, se o MDC entre "a" e "p"
é maior do que 1,

00:02:27.610 --> 00:02:30.480
eles vão compartilhar de 
um fator comum, correto?

00:02:30.480 --> 00:02:33.510
E, com isso, o "p" vai ser 
um número composto.

00:02:33.510 --> 00:02:36.835
Com isso, o resultado vai ser 
um número composto.

00:02:36.835 --> 00:02:38.427
Agora, se tivermos.

00:02:38.427 --> 00:02:41.088
Sim, podemos responder à pergunta-chave.

00:02:41.088 --> 00:02:45.530
"aᵖ⁻¹ mod p = 1?

00:02:45.530 --> 00:02:48.690
Se não, vamos ter que "p" é composto,

00:02:48.690 --> 00:02:49.974
e paramos por aqui.

00:02:49.974 --> 00:02:53.399
Caso contrário, se a equação 
for igual a 1,

00:02:53.399 --> 00:02:55.530
"p" deve ser primo, correto?

00:02:55.530 --> 00:02:58.314
E eu codifiquei essa série 
de instruções aqui

00:02:58.314 --> 00:02:59.929
e vamos ver o que acontece?

00:02:59.929 --> 00:03:03.060
Do lado esquerdo,
nós temos o teste de Fermat.

00:03:03.060 --> 00:03:07.920
Do lado direito, nós temos 
o teste de divisão experimental.

00:03:07.920 --> 00:03:11.040
Veja que parece que sempre vai dar certo.

00:03:11.040 --> 00:03:15.389
Só de olhar você consegue ver que 
os valores são sempre os mesmos,

00:03:15.389 --> 00:03:19.110
não importa o valor que eu 
modifique no meu algoritmo.

00:03:19.110 --> 00:03:21.660
Porém, eu encontro um problema aqui.

00:03:21.660 --> 00:03:24.620
Eu coloquei o número 511

00:03:24.620 --> 00:03:28.050
e o Teorema de Fermat está 
dizendo que é primo.

00:03:28.050 --> 00:03:32.465
Já o teste da divisão experimental, 
diz que é composto.

00:03:32.465 --> 00:03:34.392
O que será que está acontecendo?

00:03:34.392 --> 00:03:37.690
O 511, de fato, não é um número primo.

00:03:37.690 --> 00:03:41.470
E vamos voltar aqui na nossa equação 
e ver o que aconteceu.

00:03:41.470 --> 00:03:45.540
Este é um exemplo do que 
chamamos de falso primo.

00:03:45.540 --> 00:03:48.700
É um número composto,
mas existem alguns "a"

00:03:48.700 --> 00:03:51.340
que escolhemos que resultam em 1.

00:03:51.340 --> 00:03:54.239
E eles são chamados de enganadores.

00:03:54.239 --> 00:03:59.420
Isso porque eles nos fazem pensar 
que a resposta é um número primo.

00:03:59.420 --> 00:04:01.339
E note que mudando o "a",

00:04:01.339 --> 00:04:04.044
encontramos muitos 
números compostos

00:04:04.044 --> 00:04:06.189
que eu vou chamar 
de testemunhas.

00:04:06.189 --> 00:04:08.340
Eles não são enganadores.

00:04:08.340 --> 00:04:14.470
Agora, podemos utilizar a mesma lógica 
que usamos no teste de divisibilidade,

00:04:14.470 --> 00:04:16.420
onde geramos um novo "a"

00:04:16.420 --> 00:04:19.840
e torcemos para não encontrar 
um enganador.

00:04:19.840 --> 00:04:23.790
Agora, nós conseguimos ver que 
estes enganadores

00:04:23.790 --> 00:04:28.410
dividem o número total do grupo 
que estamos selecionando.

00:04:28.410 --> 00:04:32.660
Isso significa que no máximo 
metade das escolhas

00:04:32.660 --> 00:04:36.500
ou metade dos elementos 
selecionados neste grupo,

00:04:36.500 --> 00:04:38.610
podem ser enganadores.

00:04:38.610 --> 00:04:42.550
Então, desde que o "a" 
seja encontrado aleatoriamente,

00:04:42.550 --> 00:04:45.119
a chance de encontrar uma testemunha,

00:04:45.119 --> 00:04:48.411
que é o que queremos,
é pelo menos a metade.

00:04:48.411 --> 00:04:50.749
E depois de ter repetições,

00:04:50.749 --> 00:04:54.766
a probabilidade de que nenhuma 
testemunha seja encontrada

00:04:54.766 --> 00:05:00.929
com um número composto é 
no máximo 1/2ᵗ.

00:05:00.929 --> 00:05:04.139
Depois de 20 tentativas, 
por exemplo,

00:05:04.139 --> 00:05:07.894
a probabilidade de sair um 
número primo erroneamente

00:05:07.894 --> 00:05:11.119
é de uma em um milhão, 
aproximadamente.

00:05:11.119 --> 00:05:15.369
É aquele caso onde continuamos 
com uma má sorte

00:05:15.369 --> 00:05:18.164
em gerar os "a" aleatórios

00:05:18.164 --> 00:05:21.052
e toda vez encontramos um enganador.

00:05:21.052 --> 00:05:24.376
E agora sim podemos ver 
nosso teste em ação.

00:05:24.376 --> 00:05:26.616
Com o maior número de tentativas,

00:05:26.616 --> 00:05:30.430
parece que o teste está funcionando 
perfeitamente, correto?

00:05:30.430 --> 00:05:32.549
Note que, no pior caso,

00:05:32.549 --> 00:05:36.599
que sabemos que é quando temos 
um algoritmo com este primo,

00:05:36.599 --> 00:05:41.070
a máquina vai ter um trabalho muito 
grande para gerar o teste de Fermat.

00:05:41.070 --> 00:05:45.089
É muito mais eficiente que 
a divisão experimental.

00:05:45.089 --> 00:05:46.189
Principalmente,

00:05:46.189 --> 00:05:49.800
porque o número de passos 
não aumenta com a entrada.

00:05:49.800 --> 00:05:50.654
Por exemplo,

00:05:50.654 --> 00:05:54.787
graficamente relacionando 
o tempo e o tamanho da entrada,

00:05:54.787 --> 00:05:57.490
vai ser algo, mais ou menos, assim.

00:05:57.490 --> 00:06:02.115
Basicamente, no teste de Fermat 
nunca temos que nos preocupar

00:06:02.115 --> 00:06:05.982
com o algoritmo rodando milhões 
e milhões de vezes

00:06:05.982 --> 00:06:08.620
de repetições como fizemos antes.

00:06:08.620 --> 00:06:14.068
Então, o que eu quero dizer é que isso 
nada mais é do que matemática aplicada.

00:06:14.068 --> 00:06:17.620
Ou seja, pegamos um padrão 
que alguém descobriu

00:06:17.620 --> 00:06:22.105
e colocamos uma grande quantidade 
de repetições no computador,

00:06:22.105 --> 00:06:24.267
isso através de programação.

00:06:24.267 --> 00:06:26.310
Mas, neste sistema aqui,

00:06:26.310 --> 00:06:27.847
tem uma pequena falha.

00:06:27.847 --> 00:06:29.844
Será que você consegue encontrar?

00:06:29.844 --> 00:06:32.462
Eu vou deixar aqui como 
exercício e pesquisa.

00:06:32.462 --> 00:06:36.055
Então, não perca tempo 
e tente buscar a resposta.

00:06:36.055 --> 00:06:38.540
Eu espero que esta aula 
tenha lhes ajudado

00:06:38.540 --> 00:06:41.090
e até a próxima, pessoal!