[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:02.94,Default,,0000,0000,0000,,RKA 3 - E aí, pessoal, tudo bem?
Dialogue: 0,0:00:02.94,0:00:06.09,Default,,0000,0000,0000,,Nesta aula, vamos fazer o teste \Nde primalidade de Fermat.
Dialogue: 0,0:00:06.09,0:00:09.09,Default,,0000,0000,0000,,Para isso, vamos determinar uma
Dialogue: 0,0:00:09.09,0:00:11.73,Default,,0000,0000,0000,,série de instruções que possam provar
Dialogue: 0,0:00:11.73,0:00:14.34,Default,,0000,0000,0000,,se um número inteiro de \Nentrada é composto ou primo
Dialogue: 0,0:00:14.34,0:00:17.76,Default,,0000,0000,0000,,com alto grau de precisão.
Dialogue: 0,0:00:17.76,0:00:20.31,Default,,0000,0000,0000,,Claro, seria mais fácil calcular isso
Dialogue: 0,0:00:20.31,0:00:22.71,Default,,0000,0000,0000,,em qualquer máquina.\NE mesmo que um número
Dialogue: 0,0:00:22.71,0:00:25.53,Default,,0000,0000,0000,,de entrada aumente,\Nisso ainda deveria
Dialogue: 0,0:00:25.53,0:00:28.53,Default,,0000,0000,0000,,ser mais rápido, correto?\NAté agora nós aprendemos
Dialogue: 0,0:00:28.53,0:00:31.29,Default,,0000,0000,0000,,que precisamos reconhecer um padrão
Dialogue: 0,0:00:31.29,0:00:34.35,Default,,0000,0000,0000,,que todos os números primos têm
Dialogue: 0,0:00:34.35,0:00:37.20,Default,,0000,0000,0000,,e que alguns compostos não. \NE no vídeo em que
Dialogue: 0,0:00:37.20,0:00:39.54,Default,,0000,0000,0000,,fizemos uma demonstração visual do
Dialogue: 0,0:00:39.54,0:00:42.00,Default,,0000,0000,0000,,Teorema de Fermat,\Nvimos uma regra
Dialogue: 0,0:00:42.00,0:00:44.52,Default,,0000,0000,0000,,bastante interessante que era,
Dialogue: 0,0:00:44.52,0:00:47.61,Default,,0000,0000,0000,,dado um número primo "p" e o inteiro "a",
Dialogue: 0,0:00:47.61,0:00:51.44,Default,,0000,0000,0000,,que é menor do que "p".\NSabemos que "p" divide "a"
Dialogue: 0,0:00:51.44,0:00:56.42,Default,,0000,0000,0000,,elevado a p - a.\NE escrevemos isso como,
Dialogue: 0,0:00:56.42,0:01:01.33,Default,,0000,0000,0000,,"a" elevado a "p mod p.\NGeralmente, você encontra
Dialogue: 0,0:01:01.33,0:01:04.06,Default,,0000,0000,0000,,o teorema deste jeito.\NE como "a" e "p"
Dialogue: 0,0:01:04.06,0:01:07.36,Default,,0000,0000,0000,,não tem um fator comum.\NJá que "p" é primo,
Dialogue: 0,0:01:07.36,0:01:10.42,Default,,0000,0000,0000,,podemos cancelar estes elementos.
Dialogue: 0,0:01:10.42,0:01:13.38,Default,,0000,0000,0000,,E, às vezes, você vai encontrar escrito
Dialogue: 0,0:01:13.38,0:01:18.73,Default,,0000,0000,0000,,"a" elevado a p - 1 = 1 mod p.
Dialogue: 0,0:01:18.73,0:01:21.40,Default,,0000,0000,0000,,E lembre-se que só podemos fazer isso,\Nporque o maior
Dialogue: 0,0:01:21.40,0:01:25.00,Default,,0000,0000,0000,,divisor comum entre "a" e "p" é 1.
Dialogue: 0,0:01:25.00,0:01:27.46,Default,,0000,0000,0000,,Agora, podemos ver uma demonstração de
Dialogue: 0,0:01:27.46,0:01:29.59,Default,,0000,0000,0000,,como isso funciona\Npara entender melhor o processo.
Dialogue: 0,0:01:29.59,0:01:32.50,Default,,0000,0000,0000,,Note que se você colocar um
Dialogue: 0,0:01:32.50,0:01:36.01,Default,,0000,0000,0000,,número primo para o "p",\No resultado vai ser sempre igual a 1,
Dialogue: 0,0:01:36.01,0:01:38.53,Default,,0000,0000,0000,,não importa o "a"
Dialogue: 0,0:01:38.53,0:01:41.14,Default,,0000,0000,0000,,que você escolha.\NMas se colocarmos um
Dialogue: 0,0:01:41.14,0:01:44.05,Default,,0000,0000,0000,,número composto para o "p",\Npodemos ver que
Dialogue: 0,0:01:44.05,0:01:46.87,Default,,0000,0000,0000,,normalmente o resultado não vai ser 1.
Dialogue: 0,0:01:46.87,0:01:49.63,Default,,0000,0000,0000,,A maioria das vezes vai ser diferente de 1.
Dialogue: 0,0:01:49.63,0:01:52.90,Default,,0000,0000,0000,,O resultado vai ser composto.
Dialogue: 0,0:01:52.90,0:01:55.33,Default,,0000,0000,0000,,Isto é uma prova de que o "p"\Nque escolhemos não pode ser primo.
Dialogue: 0,0:01:55.33,0:01:58.57,Default,,0000,0000,0000,,Essa é essência do teste.
Dialogue: 0,0:01:58.57,0:02:01.19,Default,,0000,0000,0000,,E antes de prosseguir,\Nvamos construir
Dialogue: 0,0:02:01.19,0:02:05.06,Default,,0000,0000,0000,,uma estrutura aqui para ele utilizando o
Dialogue: 0,0:02:05.06,0:02:07.73,Default,,0000,0000,0000,,padrão que eu mostrei.\NPrimeiro, nós temos
Dialogue: 0,0:02:07.73,0:02:10.49,Default,,0000,0000,0000,,uma entrada que vai ser um número
Dialogue: 0,0:02:10.49,0:02:14.09,Default,,0000,0000,0000,,inteiro "p".\NDepois geramos um número
Dialogue: 0,0:02:14.09,0:02:16.88,Default,,0000,0000,0000,,inteiro aleatório que é menor do que o "p" escolhido.
Dialogue: 0,0:02:16.88,0:02:20.18,Default,,0000,0000,0000,,E aí, perguntamos, o maior
Dialogue: 0,0:02:20.18,0:02:24.32,Default,,0000,0000,0000,,divisor comum entre "a" e "p" é 1?
Dialogue: 0,0:02:24.32,0:02:27.53,Default,,0000,0000,0000,,Se não, ou seja, se o MDC entre "a" e "p"\Né maior do que 1,
Dialogue: 0,0:02:27.53,0:02:29.81,Default,,0000,0000,0000,,eles vão compartilhar de um fator comum, correto?
Dialogue: 0,0:02:29.81,0:02:32.96,Default,,0000,0000,0000,,E, com isso, o "p" vai ser um
Dialogue: 0,0:02:32.96,0:02:35.87,Default,,0000,0000,0000,,número composto.\NCom isso, o resultado vai
Dialogue: 0,0:02:35.87,0:02:38.63,Default,,0000,0000,0000,,ser um número composto.\NAgora, se tivermos.
Dialogue: 0,0:02:38.63,0:02:41.12,Default,,0000,0000,0000,,Sim, podemos responder à pergunta a chave.
Dialogue: 0,0:02:41.12,0:02:45.59,Default,,0000,0000,0000,,"a" elevado a p - 1 mod p é igual a 1?
Dialogue: 0,0:02:45.59,0:02:49.25,Default,,0000,0000,0000,,Se não, vamos ter que "p" é composto,
Dialogue: 0,0:02:49.25,0:02:52.10,Default,,0000,0000,0000,,e paramos por aqui.\NCaso contrário, se a
Dialogue: 0,0:02:52.10,0:02:55.16,Default,,0000,0000,0000,,equação for igual a 1,\N"p" deve ser primo, correto?
Dialogue: 0,0:02:55.16,0:02:57.62,Default,,0000,0000,0000,,E eu codifiquei essa série de
Dialogue: 0,0:02:57.62,0:02:59.57,Default,,0000,0000,0000,,instruções aqui e vamos ver o que acontece?
Dialogue: 0,0:02:59.57,0:03:02.37,Default,,0000,0000,0000,,Do lado esquerdo,\Nnós temos o teste de Fermat.
Dialogue: 0,0:03:02.37,0:03:04.92,Default,,0000,0000,0000,,Do lado direito, nós temos
Dialogue: 0,0:03:04.92,0:03:08.03,Default,,0000,0000,0000,,o teste de divisão experimental.
Dialogue: 0,0:03:08.03,0:03:11.22,Default,,0000,0000,0000,,Veja que parece que sempre vai dar certo.
Dialogue: 0,0:03:11.22,0:03:14.01,Default,,0000,0000,0000,,Só de olhar você consegue ver que os
Dialogue: 0,0:03:14.01,0:03:16.74,Default,,0000,0000,0000,,valores são sempre os mesmos,
Dialogue: 0,0:03:16.74,0:03:18.69,Default,,0000,0000,0000,,não importa o valor que \Neu modifique no meu algoritmo.
Dialogue: 0,0:03:18.69,0:03:21.66,Default,,0000,0000,0000,,Porém, eu encontro um problema aqui.
Dialogue: 0,0:03:21.66,0:03:25.41,Default,,0000,0000,0000,,Eu coloquei o número 511 e o
Dialogue: 0,0:03:25.41,0:03:27.90,Default,,0000,0000,0000,,Teorema de Fermat está dizendo que é primo.
Dialogue: 0,0:03:27.90,0:03:31.32,Default,,0000,0000,0000,,Já o teste da divisão experimental,
Dialogue: 0,0:03:31.32,0:03:33.93,Default,,0000,0000,0000,,diz que é composto.\NO que será que está acontecendo?
Dialogue: 0,0:03:33.93,0:03:37.23,Default,,0000,0000,0000,,O 511, de fato, não é um número primo.
Dialogue: 0,0:03:37.23,0:03:39.54,Default,,0000,0000,0000,,E vamos voltar aqui na
Dialogue: 0,0:03:39.54,0:03:42.45,Default,,0000,0000,0000,,nossa equação e ver o que aconteceu.
Dialogue: 0,0:03:42.45,0:03:45.33,Default,,0000,0000,0000,,Este é um exemplo do que chamamos de falso primo.
Dialogue: 0,0:03:45.33,0:03:48.45,Default,,0000,0000,0000,,É um número composto,\Nmas existem alguns "a"
Dialogue: 0,0:03:48.45,0:03:51.42,Default,,0000,0000,0000,,que escolhemos que resultam em 1.
Dialogue: 0,0:03:51.42,0:03:54.24,Default,,0000,0000,0000,,E eles são chamados de enganadores.
Dialogue: 0,0:03:54.24,0:03:57.60,Default,,0000,0000,0000,,Isso porque eles nos fazem pensar que a
Dialogue: 0,0:03:57.60,0:04:00.01,Default,,0000,0000,0000,,resposta é um número primo.
Dialogue: 0,0:04:00.01,0:04:03.19,Default,,0000,0000,0000,,E note que mudando o "a", \Nencontramos muitos
Dialogue: 0,0:04:03.19,0:04:05.55,Default,,0000,0000,0000,,números compostos que eu \Nvou chamar de testemunhas.
Dialogue: 0,0:04:05.55,0:04:08.47,Default,,0000,0000,0000,,Eles não são enganadores.
Dialogue: 0,0:04:08.47,0:04:11.59,Default,,0000,0000,0000,,Agora, podemos utilizar a mesma lógica
Dialogue: 0,0:04:11.59,0:04:14.28,Default,,0000,0000,0000,,que usamos no teste de divisibilidade,
Dialogue: 0,0:04:14.28,0:04:17.89,Default,,0000,0000,0000,,onde geramos um novo "a"\Ne torcemos para
Dialogue: 0,0:04:17.89,0:04:21.22,Default,,0000,0000,0000,,não encontrar um enganador.
Dialogue: 0,0:04:21.22,0:04:24.09,Default,,0000,0000,0000,,Agora, nós conseguimos ver que \Nestes enganadores
Dialogue: 0,0:04:24.09,0:04:27.10,Default,,0000,0000,0000,,dividem o número total do grupo que
Dialogue: 0,0:04:27.10,0:04:30.52,Default,,0000,0000,0000,,estamos selecionando.\NIsso significa que
Dialogue: 0,0:04:30.52,0:04:34.12,Default,,0000,0000,0000,,no máximo metade das escolhas ou
Dialogue: 0,0:04:34.12,0:04:36.94,Default,,0000,0000,0000,,metade dos elementos selecionados neste grupo,
Dialogue: 0,0:04:36.94,0:04:40.30,Default,,0000,0000,0000,,podem ser enganadores.\NEntão, desde que o "a"
Dialogue: 0,0:04:40.30,0:04:43.15,Default,,0000,0000,0000,,seja encontrado aleatoriamente,
Dialogue: 0,0:04:43.15,0:04:45.79,Default,,0000,0000,0000,,a chance de encontrar uma testemunha,
Dialogue: 0,0:04:45.79,0:04:48.94,Default,,0000,0000,0000,,que é o que queremos,\Né pelo menos a metade.
Dialogue: 0,0:04:48.94,0:04:52.48,Default,,0000,0000,0000,,E depois de ter repetições,\Na probabilidade de que
Dialogue: 0,0:04:52.48,0:04:54.37,Default,,0000,0000,0000,,nenhuma testemunha seja
Dialogue: 0,0:04:54.37,0:04:57.67,Default,,0000,0000,0000,,encontrada com um número composto é no máximo 1/2 elevado a "t".
Dialogue: 0,0:04:57.67,0:05:02.84,Default,,0000,0000,0000,,Depois de 20 tentativas,
Dialogue: 0,0:05:02.84,0:05:05.87,Default,,0000,0000,0000,,por exemplo, a probabilidade
Dialogue: 0,0:05:05.87,0:05:08.54,Default,,0000,0000,0000,,de sair um número primo erroneamente é
Dialogue: 0,0:05:08.54,0:05:10.48,Default,,0000,0000,0000,,de uma em um milhão, aproximadamente.
Dialogue: 0,0:05:10.48,0:05:13.22,Default,,0000,0000,0000,,É aquele caso onde
Dialogue: 0,0:05:13.22,0:05:16.82,Default,,0000,0000,0000,,continuamos com uma má sorte em gerar
Dialogue: 0,0:05:16.82,0:05:20.18,Default,,0000,0000,0000,,os "a" aleatórios e\Ntoda vez encontramos
Dialogue: 0,0:05:20.18,0:05:23.21,Default,,0000,0000,0000,,um enganador.\NE agora sim podemos ver
Dialogue: 0,0:05:23.21,0:05:25.61,Default,,0000,0000,0000,,nosso teste em ação. \NCom o maior número de tentativas,
Dialogue: 0,0:05:25.61,0:05:28.64,Default,,0000,0000,0000,,parece que o teste está
Dialogue: 0,0:05:28.64,0:05:31.52,Default,,0000,0000,0000,,funcionando perfeitamente, correto?
Dialogue: 0,0:05:31.52,0:05:34.10,Default,,0000,0000,0000,,Note que no pior caso,\Nque sabemos que é
Dialogue: 0,0:05:34.10,0:05:36.98,Default,,0000,0000,0000,,quando temos um algoritmo com este primo,
Dialogue: 0,0:05:36.98,0:05:38.90,Default,,0000,0000,0000,,a máquina vai ter um trabalho muito
Dialogue: 0,0:05:38.90,0:05:41.63,Default,,0000,0000,0000,,grande para gerar o teste de Fermat.
Dialogue: 0,0:05:41.63,0:05:44.32,Default,,0000,0000,0000,,É muito mais eficiente que a divisão experimental.
Dialogue: 0,0:05:44.32,0:05:47.18,Default,,0000,0000,0000,,Principalmente, porque o
Dialogue: 0,0:05:47.18,0:05:49.40,Default,,0000,0000,0000,,número de passos não aumenta com a entrada.
Dialogue: 0,0:05:49.40,0:05:51.97,Default,,0000,0000,0000,,Por exemplo, graficamente
Dialogue: 0,0:05:51.97,0:05:54.53,Default,,0000,0000,0000,,relacionando o tempo e o tamanho da
Dialogue: 0,0:05:54.53,0:05:57.49,Default,,0000,0000,0000,,entrada vai ser algo, mais ou menos, assim.
Dialogue: 0,0:05:57.49,0:06:01.05,Default,,0000,0000,0000,,Basicamente, no teste de Fermat nunca
Dialogue: 0,0:06:01.05,0:06:03.17,Default,,0000,0000,0000,,temos que nos preocupar com o algoritmo
Dialogue: 0,0:06:03.17,0:06:06.36,Default,,0000,0000,0000,,rodando milhões e milhões de vezes de
Dialogue: 0,0:06:06.36,0:06:09.72,Default,,0000,0000,0000,,repetições como fizemos antes.
Dialogue: 0,0:06:09.72,0:06:12.27,Default,,0000,0000,0000,,Então, o que eu quero dizer é \Nque isso nada mais
Dialogue: 0,0:06:12.27,0:06:14.88,Default,,0000,0000,0000,,é do que matemática aplicada.
Dialogue: 0,0:06:14.88,0:06:18.18,Default,,0000,0000,0000,,Ou seja, pegamos um padrão \Nque alguém descobriu e
Dialogue: 0,0:06:18.18,0:06:20.94,Default,,0000,0000,0000,,colocamos uma grande quantidade de
Dialogue: 0,0:06:20.94,0:06:23.88,Default,,0000,0000,0000,,repetições no computador,\Nisso através de programação.
Dialogue: 0,0:06:23.88,0:06:27.06,Default,,0000,0000,0000,,Mas, neste sistema aqui, tem
Dialogue: 0,0:06:27.06,0:06:29.40,Default,,0000,0000,0000,,uma pequena falha.\NSerá que você consegue encontrar?
Dialogue: 0,0:06:29.40,0:06:31.47,Default,,0000,0000,0000,,Eu vou deixar aqui como
Dialogue: 0,0:06:31.47,0:06:34.08,Default,,0000,0000,0000,,exercício e pesquisa.\NEntão, não perca tempo e
Dialogue: 0,0:06:34.08,0:06:36.84,Default,,0000,0000,0000,,tente buscar a resposta.
Dialogue: 0,0:06:36.84,0:06:39.12,Default,,0000,0000,0000,,E eu espero que esta \Naula tenha te ajudado e
Dialogue: 0,0:06:39.12,0:06:42.32,Default,,0000,0000,0000,,até a próxima pessoal!