1
00:00:00,000 --> 00:00:01,769
RKA3JV - E aí, pessoal! 
Tudo bem?

2
00:00:01,769 --> 00:00:06,359
Nesta aula, vamos fazer o teste 
de primalidade de Fermat.

3
00:00:06,359 --> 00:00:11,211
Para isso, vamos determinar uma série 
de instruções que possam provar

4
00:00:11,211 --> 00:00:13,987
se um número inteiro de entrada é composto

5
00:00:13,987 --> 00:00:16,830
ou primo com alto grau de precisão.

6
00:00:16,830 --> 00:00:21,003
Claro, seria mais fácil calcular isso 
em qualquer máquina.

7
00:00:21,003 --> 00:00:23,842
E mesmo que um número 
de entrada aumente,

8
00:00:23,842 --> 00:00:26,635
isso ainda deveria ser mais rápido, 
correto?

9
00:00:26,635 --> 00:00:31,409
Até agora nós aprendemos que 
precisamos reconhecer um padrão

10
00:00:31,409 --> 00:00:33,833
que todos os números primos têm,

11
00:00:33,833 --> 00:00:35,722
e que alguns compostos não.

12
00:00:35,722 --> 00:00:40,449
E no vídeo em que fizemos uma 
demonstração visual do Teorema de Fermat,

13
00:00:40,449 --> 00:00:43,009
vimos uma regra bastante interessante

14
00:00:43,009 --> 00:00:45,607
que era, dado um número primo "p"

15
00:00:45,607 --> 00:00:48,505
e o inteiro "a", que é menor do que "p",

16
00:00:48,505 --> 00:00:53,602
sabemos que "p" divide "aᵖ - a".

17
00:00:53,602 --> 00:00:58,827
E escrevemos isso como, "aᵖ = a mod p".

18
00:00:58,827 --> 00:01:02,544
Geralmente, você encontra 
o teorema deste jeito.

19
00:01:02,544 --> 00:01:06,940
E como "a" e "p" não têm um fator comum, 
já que "p" é primo,

20
00:01:06,940 --> 00:01:09,408
podemos cancelar estes elementos.

21
00:01:09,408 --> 00:01:17,659
E, às vezes, você vai encontrar escrito 
"aᵖ⁻¹ = 1 mod p".

22
00:01:17,659 --> 00:01:20,064
E lembre-se de que só podemos fazer isso,

23
00:01:20,064 --> 00:01:23,910
porque o maior divisor comum 
entre "a" e "p" é 1.

24
00:01:23,910 --> 00:01:27,971
Agora, podemos ver uma demonstração 
de como isso funciona

25
00:01:27,971 --> 00:01:30,010
para entender melhor o processo.

26
00:01:30,010 --> 00:01:34,149
Note que se você colocar um 
número primo para o "p",

27
00:01:34,149 --> 00:01:36,939
o resultado vai ser sempre igual a 1,

28
00:01:36,939 --> 00:01:39,104
não importa o "a" que você escolha.

29
00:01:39,104 --> 00:01:42,389
Mas, se colocarmos um número 
composto para o "p",

30
00:01:42,389 --> 00:01:46,238
podemos ver que normalmente 
o resultado não vai ser 1.

31
00:01:46,238 --> 00:01:49,540
A maioria das vezes 
vai ser diferente de 1.

32
00:01:49,540 --> 00:01:51,789
O resultado vai ser composto.

33
00:01:51,789 --> 00:01:55,918
Isto é uma prova de que o "p"
que escolhemos não pode ser primo.

34
00:01:55,918 --> 00:01:58,139
Essa é essência do teste.

35
00:01:58,139 --> 00:01:59,954
E antes de prosseguir,

36
00:01:59,954 --> 00:02:03,447
vamos construir uma estrutura 
aqui para ele

37
00:02:03,447 --> 00:02:06,133
utilizando o padrão 
que eu mostrei.

38
00:02:06,133 --> 00:02:11,276
Primeiro, nós temos uma entrada 
que vai ser um número inteiro "p".

39
00:02:11,276 --> 00:02:15,111
Depois, geramos um número 
inteiro aleatório

40
00:02:15,111 --> 00:02:17,679
que é menor do que o "p" escolhido.

41
00:02:17,679 --> 00:02:19,159
E aí, perguntamos:

42
00:02:19,159 --> 00:02:22,851
o maior divisor comum 
entre "a" e "p" é 1?

43
00:02:22,851 --> 00:02:27,610
Se não, ou seja, se o MDC entre "a" e "p"
é maior do que 1,

44
00:02:27,610 --> 00:02:30,480
eles vão compartilhar de 
um fator comum, correto?

45
00:02:30,480 --> 00:02:33,510
E, com isso, o "p" vai ser 
um número composto.

46
00:02:33,510 --> 00:02:36,835
Com isso, o resultado vai ser 
um número composto.

47
00:02:36,835 --> 00:02:38,427
Agora, se tivermos.

48
00:02:38,427 --> 00:02:41,088
Sim, podemos responder à pergunta-chave.

49
00:02:41,088 --> 00:02:45,530
"aᵖ⁻¹ mod p = 1?

50
00:02:45,530 --> 00:02:48,690
Se não, vamos ter que "p" é composto,

51
00:02:48,690 --> 00:02:49,974
e paramos por aqui.

52
00:02:49,974 --> 00:02:53,399
Caso contrário, se a equação 
for igual a 1,

53
00:02:53,399 --> 00:02:55,530
"p" deve ser primo, correto?

54
00:02:55,530 --> 00:02:58,314
E eu codifiquei essa série 
de instruções aqui

55
00:02:58,314 --> 00:02:59,929
e vamos ver o que acontece?

56
00:02:59,929 --> 00:03:03,060
Do lado esquerdo,
nós temos o teste de Fermat.

57
00:03:03,060 --> 00:03:07,920
Do lado direito, nós temos 
o teste de divisão experimental.

58
00:03:07,920 --> 00:03:11,040
Veja que parece que sempre vai dar certo.

59
00:03:11,040 --> 00:03:15,389
Só de olhar você consegue ver que 
os valores são sempre os mesmos,

60
00:03:15,389 --> 00:03:19,110
não importa o valor que eu 
modifique no meu algoritmo.

61
00:03:19,110 --> 00:03:21,660
Porém, eu encontro um problema aqui.

62
00:03:21,660 --> 00:03:24,620
Eu coloquei o número 511

63
00:03:24,620 --> 00:03:28,050
e o Teorema de Fermat está 
dizendo que é primo.

64
00:03:28,050 --> 00:03:32,465
Já o teste da divisão experimental, 
diz que é composto.

65
00:03:32,465 --> 00:03:34,392
O que será que está acontecendo?

66
00:03:34,392 --> 00:03:37,690
O 511, de fato, não é um número primo.

67
00:03:37,690 --> 00:03:41,470
E vamos voltar aqui na nossa equação 
e ver o que aconteceu.

68
00:03:41,470 --> 00:03:45,540
Este é um exemplo do que 
chamamos de falso primo.

69
00:03:45,540 --> 00:03:48,700
É um número composto,
mas existem alguns "a"

70
00:03:48,700 --> 00:03:51,340
que escolhemos que resultam em 1.

71
00:03:51,340 --> 00:03:54,239
E eles são chamados de enganadores.

72
00:03:54,239 --> 00:03:59,420
Isso porque eles nos fazem pensar 
que a resposta é um número primo.

73
00:03:59,420 --> 00:04:01,339
E note que mudando o "a",

74
00:04:01,339 --> 00:04:04,044
encontramos muitos 
números compostos

75
00:04:04,044 --> 00:04:06,189
que eu vou chamar 
de testemunhas.

76
00:04:06,189 --> 00:04:08,340
Eles não são enganadores.

77
00:04:08,340 --> 00:04:14,470
Agora, podemos utilizar a mesma lógica 
que usamos no teste de divisibilidade,

78
00:04:14,470 --> 00:04:16,420
onde geramos um novo "a"

79
00:04:16,420 --> 00:04:19,840
e torcemos para não encontrar 
um enganador.

80
00:04:19,840 --> 00:04:23,790
Agora, nós conseguimos ver que 
estes enganadores

81
00:04:23,790 --> 00:04:28,410
dividem o número total do grupo 
que estamos selecionando.

82
00:04:28,410 --> 00:04:32,660
Isso significa que no máximo 
metade das escolhas

83
00:04:32,660 --> 00:04:36,500
ou metade dos elementos 
selecionados neste grupo,

84
00:04:36,500 --> 00:04:38,610
podem ser enganadores.

85
00:04:38,610 --> 00:04:42,550
Então, desde que o "a" 
seja encontrado aleatoriamente,

86
00:04:42,550 --> 00:04:45,119
a chance de encontrar uma testemunha,

87
00:04:45,119 --> 00:04:48,411
que é o que queremos,
é pelo menos a metade.

88
00:04:48,411 --> 00:04:50,749
E depois de ter repetições,

89
00:04:50,749 --> 00:04:54,766
a probabilidade de que nenhuma 
testemunha seja encontrada

90
00:04:54,766 --> 00:05:00,929
com um número composto é 
no máximo 1/2ᵗ.

91
00:05:00,929 --> 00:05:04,139
Depois de 20 tentativas, 
por exemplo,

92
00:05:04,139 --> 00:05:07,894
a probabilidade de sair um 
número primo erroneamente

93
00:05:07,894 --> 00:05:11,119
é de uma em um milhão, 
aproximadamente.

94
00:05:11,119 --> 00:05:15,369
É aquele caso onde continuamos 
com uma má sorte

95
00:05:15,369 --> 00:05:18,164
em gerar os "a" aleatórios

96
00:05:18,164 --> 00:05:21,052
e toda vez encontramos um enganador.

97
00:05:21,052 --> 00:05:24,376
E agora sim podemos ver 
nosso teste em ação.

98
00:05:24,376 --> 00:05:26,616
Com o maior número de tentativas,

99
00:05:26,616 --> 00:05:30,430
parece que o teste está funcionando 
perfeitamente, correto?

100
00:05:30,430 --> 00:05:32,549
Note que, no pior caso,

101
00:05:32,549 --> 00:05:36,599
que sabemos que é quando temos 
um algoritmo com este primo,

102
00:05:36,599 --> 00:05:41,070
a máquina vai ter um trabalho muito 
grande para gerar o teste de Fermat.

103
00:05:41,070 --> 00:05:45,089
É muito mais eficiente que 
a divisão experimental.

104
00:05:45,089 --> 00:05:46,189
Principalmente,

105
00:05:46,189 --> 00:05:49,800
porque o número de passos 
não aumenta com a entrada.

106
00:05:49,800 --> 00:05:50,654
Por exemplo,

107
00:05:50,654 --> 00:05:54,787
graficamente relacionando 
o tempo e o tamanho da entrada,

108
00:05:54,787 --> 00:05:57,490
vai ser algo, mais ou menos, assim.

109
00:05:57,490 --> 00:06:02,115
Basicamente, no teste de Fermat 
nunca temos que nos preocupar

110
00:06:02,115 --> 00:06:05,982
com o algoritmo rodando milhões 
e milhões de vezes

111
00:06:05,982 --> 00:06:08,620
de repetições como fizemos antes.

112
00:06:08,620 --> 00:06:14,068
Então, o que eu quero dizer é que isso 
nada mais é do que matemática aplicada.

113
00:06:14,068 --> 00:06:17,620
Ou seja, pegamos um padrão 
que alguém descobriu

114
00:06:17,620 --> 00:06:22,105
e colocamos uma grande quantidade 
de repetições no computador,

115
00:06:22,105 --> 00:06:24,267
isso através de programação.

116
00:06:24,267 --> 00:06:26,310
Mas, neste sistema aqui,

117
00:06:26,310 --> 00:06:27,847
tem uma pequena falha.

118
00:06:27,847 --> 00:06:29,844
Será que você consegue encontrar?

119
00:06:29,844 --> 00:06:32,462
Eu vou deixar aqui como 
exercício e pesquisa.

120
00:06:32,462 --> 00:06:36,055
Então, não perca tempo 
e tente buscar a resposta.

121
00:06:36,055 --> 00:06:38,540
Eu espero que esta aula 
tenha lhes ajudado

122
00:06:38,540 --> 00:06:41,090
e até a próxima, pessoal!