0:00:00.000,0:00:01.769
RKA3JV - E aí, pessoal! [br]Tudo bem?

0:00:01.769,0:00:06.359
Nesta aula, vamos fazer o teste [br]de primalidade de Fermat.

0:00:06.359,0:00:11.211
Para isso, vamos determinar uma série [br]de instruções que possam provar

0:00:11.211,0:00:13.987
se um número inteiro de entrada é composto

0:00:13.987,0:00:16.830
ou primo com alto grau de precisão.

0:00:16.830,0:00:21.003
Claro, seria mais fácil calcular isso [br]em qualquer máquina.

0:00:21.003,0:00:23.842
E mesmo que um número [br]de entrada aumente,

0:00:23.842,0:00:26.635
isso ainda deveria ser mais rápido, [br]correto?

0:00:26.635,0:00:31.409
Até agora nós aprendemos que [br]precisamos reconhecer um padrão

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

0:00:33.833,0:00:35.722
e que alguns compostos não.

0:00:35.722,0:00:40.449
E no vídeo em que fizemos uma [br]demonstração visual do Teorema de Fermat,

0:00:40.449,0:00:43.009
vimos uma regra bastante interessante

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

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

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

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

0:00:58.827,0:01:02.544
Geralmente, você encontra [br]o teorema deste jeito.

0:01:02.544,0:01:06.940
E como "a" e "p" não têm um fator comum, [br]já que "p" é primo,

0:01:06.940,0:01:09.408
podemos cancelar estes elementos.

0:01:09.408,0:01:17.659
E, às vezes, você vai encontrar escrito [br]"aᵖ⁻¹ = 1 mod p".

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

0:01:20.064,0:01:23.910
porque o maior divisor comum [br]entre "a" e "p" é 1.

0:01:23.910,0:01:27.971
Agora, podemos ver uma demonstração [br]de como isso funciona

0:01:27.971,0:01:30.010
para entender melhor o processo.

0:01:30.010,0:01:34.149
Note que se você colocar um [br]número primo para o "p",

0:01:34.149,0:01:36.939
o resultado vai ser sempre igual a 1,

0:01:36.939,0:01:39.104
não importa o "a" que você escolha.

0:01:39.104,0:01:42.389
Mas, se colocarmos um número [br]composto para o "p",

0:01:42.389,0:01:46.238
podemos ver que normalmente [br]o resultado não vai ser 1.

0:01:46.238,0:01:49.540
A maioria das vezes [br]vai ser diferente de 1.

0:01:49.540,0:01:51.789
O resultado vai ser composto.

0:01:51.789,0:01:55.918
Isto é uma prova de que o "p"[br]que escolhemos não pode ser primo.

0:01:55.918,0:01:58.139
Essa é essência do teste.

0:01:58.139,0:01:59.954
E antes de prosseguir,

0:01:59.954,0:02:03.447
vamos construir uma estrutura [br]aqui para ele

0:02:03.447,0:02:06.133
utilizando o padrão [br]que eu mostrei.

0:02:06.133,0:02:11.276
Primeiro, nós temos uma entrada [br]que vai ser um número inteiro "p".

0:02:11.276,0:02:15.111
Depois, geramos um número [br]inteiro aleatório

0:02:15.111,0:02:17.679
que é menor do que o "p" escolhido.

0:02:17.679,0:02:19.159
E aí, perguntamos:

0:02:19.159,0:02:22.851
o maior divisor comum [br]entre "a" e "p" é 1?

0:02:22.851,0:02:27.610
Se não, ou seja, se o MDC entre "a" e "p"[br]é maior do que 1,

0:02:27.610,0:02:30.480
eles vão compartilhar de [br]um fator comum, correto?

0:02:30.480,0:02:33.510
E, com isso, o "p" vai ser [br]um número composto.

0:02:33.510,0:02:36.835
Com isso, o resultado vai ser [br]um número composto.

0:02:36.835,0:02:38.427
Agora, se tivermos.

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

0:02:41.088,0:02:45.530
"aᵖ⁻¹ mod p = 1?

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

0:02:48.690,0:02:49.974
e paramos por aqui.

0:02:49.974,0:02:53.399
Caso contrário, se a equação [br]for igual a 1,

0:02:53.399,0:02:55.530
"p" deve ser primo, correto?

0:02:55.530,0:02:58.314
E eu codifiquei essa série [br]de instruções aqui

0:02:58.314,0:02:59.929
e vamos ver o que acontece?

0:02:59.929,0:03:03.060
Do lado esquerdo,[br]nós temos o teste de Fermat.

0:03:03.060,0:03:07.920
Do lado direito, nós temos [br]o teste de divisão experimental.

0:03:07.920,0:03:11.040
Veja que parece que sempre vai dar certo.

0:03:11.040,0:03:15.389
Só de olhar você consegue ver que [br]os valores são sempre os mesmos,

0:03:15.389,0:03:19.110
não importa o valor que eu [br]modifique no meu algoritmo.

0:03:19.110,0:03:21.660
Porém, eu encontro um problema aqui.

0:03:21.660,0:03:24.620
Eu coloquei o número 511

0:03:24.620,0:03:28.050
e o Teorema de Fermat está [br]dizendo que é primo.

0:03:28.050,0:03:32.465
Já o teste da divisão experimental, [br]diz que é composto.

0:03:32.465,0:03:34.392
O que será que está acontecendo?

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

0:03:37.690,0:03:41.470
E vamos voltar aqui na nossa equação [br]e ver o que aconteceu.

0:03:41.470,0:03:45.540
Este é um exemplo do que [br]chamamos de falso primo.

0:03:45.540,0:03:48.700
É um número composto,[br]mas existem alguns "a"

0:03:48.700,0:03:51.340
que escolhemos que resultam em 1.

0:03:51.340,0:03:54.239
E eles são chamados de enganadores.

0:03:54.239,0:03:59.420
Isso porque eles nos fazem pensar [br]que a resposta é um número primo.

0:03:59.420,0:04:01.339
E note que mudando o "a",

0:04:01.339,0:04:04.044
encontramos muitos [br]números compostos

0:04:04.044,0:04:06.189
que eu vou chamar [br]de testemunhas.

0:04:06.189,0:04:08.340
Eles não são enganadores.

0:04:08.340,0:04:14.470
Agora, podemos utilizar a mesma lógica [br]que usamos no teste de divisibilidade,

0:04:14.470,0:04:16.420
onde geramos um novo "a"

0:04:16.420,0:04:19.840
e torcemos para não encontrar [br]um enganador.

0:04:19.840,0:04:23.790
Agora, nós conseguimos ver que [br]estes enganadores

0:04:23.790,0:04:28.410
dividem o número total do grupo [br]que estamos selecionando.

0:04:28.410,0:04:32.660
Isso significa que no máximo [br]metade das escolhas

0:04:32.660,0:04:36.500
ou metade dos elementos [br]selecionados neste grupo,

0:04:36.500,0:04:38.610
podem ser enganadores.

0:04:38.610,0:04:42.550
Então, desde que o "a" [br]seja encontrado aleatoriamente,

0:04:42.550,0:04:45.119
a chance de encontrar uma testemunha,

0:04:45.119,0:04:48.411
que é o que queremos,[br]é pelo menos a metade.

0:04:48.411,0:04:50.749
E depois de ter repetições,

0:04:50.749,0:04:54.766
a probabilidade de que nenhuma [br]testemunha seja encontrada

0:04:54.766,0:05:00.929
com um número composto é [br]no máximo 1/2ᵗ.

0:05:00.929,0:05:04.139
Depois de 20 tentativas, [br]por exemplo,

0:05:04.139,0:05:07.894
a probabilidade de sair um [br]número primo erroneamente

0:05:07.894,0:05:11.119
é de uma em um milhão, [br]aproximadamente.

0:05:11.119,0:05:15.369
É aquele caso onde continuamos [br]com uma má sorte

0:05:15.369,0:05:18.164
em gerar os "a" aleatórios

0:05:18.164,0:05:21.052
e toda vez encontramos um enganador.

0:05:21.052,0:05:24.376
E agora sim podemos ver [br]nosso teste em ação.

0:05:24.376,0:05:26.616
Com o maior número de tentativas,

0:05:26.616,0:05:30.430
parece que o teste está funcionando [br]perfeitamente, correto?

0:05:30.430,0:05:32.549
Note que, no pior caso,

0:05:32.549,0:05:36.599
que sabemos que é quando temos [br]um algoritmo com este primo,

0:05:36.599,0:05:41.070
a máquina vai ter um trabalho muito [br]grande para gerar o teste de Fermat.

0:05:41.070,0:05:45.089
É muito mais eficiente que [br]a divisão experimental.

0:05:45.089,0:05:46.189
Principalmente,

0:05:46.189,0:05:49.800
porque o número de passos [br]não aumenta com a entrada.

0:05:49.800,0:05:50.654
Por exemplo,

0:05:50.654,0:05:54.787
graficamente relacionando [br]o tempo e o tamanho da entrada,

0:05:54.787,0:05:57.490
vai ser algo, mais ou menos, assim.

0:05:57.490,0:06:02.115
Basicamente, no teste de Fermat [br]nunca temos que nos preocupar

0:06:02.115,0:06:05.982
com o algoritmo rodando milhões [br]e milhões de vezes

0:06:05.982,0:06:08.620
de repetições como fizemos antes.

0:06:08.620,0:06:14.068
Então, o que eu quero dizer é que isso [br]nada mais é do que matemática aplicada.

0:06:14.068,0:06:17.620
Ou seja, pegamos um padrão [br]que alguém descobriu

0:06:17.620,0:06:22.105
e colocamos uma grande quantidade [br]de repetições no computador,

0:06:22.105,0:06:24.267
isso através de programação.

0:06:24.267,0:06:26.310
Mas, neste sistema aqui,

0:06:26.310,0:06:27.847
tem uma pequena falha.

0:06:27.847,0:06:29.844
Será que você consegue encontrar?

0:06:29.844,0:06:32.462
Eu vou deixar aqui como [br]exercício e pesquisa.

0:06:32.462,0:06:36.055
Então, não perca tempo [br]e tente buscar a resposta.

0:06:36.055,0:06:38.540
Eu espero que esta aula [br]tenha lhes ajudado

0:06:38.540,0:06:41.090
e até a próxima, pessoal!