Conteúdo principal
Tempo atual:0:00Duração total:7:09

Transcrição de vídeo

Nosso objetivo é definir uma série de instruções que podem provar se um inteiro de entrada é composto - ou então ser identificado como primo - com um grau muito alto de precisão que nós podemos definir. E precisa ser eficiente para fazer isso, significando que deve ser rápido para calcular em qualquer máquina, mesmo se o tamanho da entrada crescer, que é nosso inteiro 'n' de entrada, ainda assim deve ser rápido. E até agora, nós aprendemos que, no nível mais baixo, isso requer algum padrão conhecido que todos os números primos seguem e muitos poucos números compostos seguem. Entretanto, no vídeo anterior, nós fizemos uma demonstração visual do pequeno teorema de Fermat E isso nos deu uma regra muito interessante. Dado um número primo 'p', e um outro inteiro 'a', que é estritamente menor que 'p', nós sabemos agora que 'p' divide 'a' elevado a 'p' menos 'a'. Nós escrevemos isso como a^p = a mod p E assim é como você normalmente vê isso. Agora por 'a' e 'p' não compartilharem nenhum fator comum - já que 'p' é um primo - nós podemos usar a lei de cancelamento e algumas vezes você vai ver escrito como a^(p -1) = 1 mod p E lembre-se, nós só podemos fazer isso porque o maior divisor comum de 'a' e 'p' é igual a um. acabo de preparar uma demonstração aqui, assim nós podemos primeiro apenas ver essa equação em ação e ficar confortável com ela. Note agora, se coloco um número primo como entrada para 'p', a saída é sempre 1, não importa qual 'a' eu escolha. Se nós colocarmos um número composto como entrada para 'p', nós vemos que a saída geralmente não é um. E, a qualquer momento que essa equação resulta em algum número que não seja um, nós temos uma evidencia de que ele é um número composto. Isso é prova de que o 'p' que escolhemos não pode ser primo. E essa é a essência deste teste. E, antes de ir mais a fundo, vamos voltar um pouco e construir o arcabouço para esse teste usando esse padrão que eu acabei de mostrar a você. Então nosso teste exige que forneçamos algum inteiro, vamos chamar de 'p', como entrada. Depois, precisamoss de outro inteiro aleatóreo, 'a', que deve ser menor que 'p'. Agora podemos perguntar, "O Maior Divisor Comum entre a e p é 1?" se não for, isto é, se o maior divisor comum entre a e p é maior que 1, então eles tem um fator em comum, e provamos que 'p' é um número composto, porque o fator existe. Então podemos parar aqui, e a resposta do nosso algoritmo será composto. No entanto, se 'sim', podemos fazer a pergunta chave, "a elevado a p menos 1, módulo p, é igual a 1?" Se não, temos uma evidência de que 'p' é composto. Podemos parar e dizer, "Isso. Terminamos. p é composto." De outra forma, se 'sim', se nossa equação resulta em 1, então ele deve ser primo, certo? fiz um código com essas instruções e, temos o teste de Fermat a esquerda, e o teste de divisão a direita. E ele está la porque sabemos que esse teste não falha. A primeira vista, tudo parece estar funcionando. Mas, encontrei um problema. Cheguei no número 511, o teste de Fermat está dizendo que ele é primo, e o teste de divisão está dizendo que ele é composto. 511 parece primo da perspectiva do nosso teste. Mas não é. Vamos voltar a nossa equação, e ver o que aconteceu. Bem, esse é um exemplo do que chamamos 'pseudo-primo'. É um número composto. Mas existem certos a's que podem resultar em 1. Isso está incorreto de novo. Esses a's que fazem nossa equação responder 1 para números compostos, são chamados de 'tolos'. Porque estão nos induzindo a pensar que o número é primo. Mas note que se escolhermos a's diferentes, encontraremos muitas evidências de que ele é composto ao invés de 'tolos'. Então, vamos voltar um pouco. E aplicar a mesma lógica que usamos no teste de divisibilidade, onde simplesmente repetimos o experimento algumas vezes, usando entradas aleatóreas. Esperamos, que elas não sejam todas 'tolas'. Está provado que o número de 'tolos' deve dividir o grupo de números selecionados. Ou seja, no máximo metade deles devem ser tolos. Como 'a' é escolhido aleatóreamente, a chance de encontrar uma evidencia de composto, que é o que queremos, é pelo menos meio. Depois de t iterações, a probabilidade de não encontrar evidências com um número composto é de no máximo 1/(2^t). Depois de 20 tentativas, a probabilidade de se enganar quanto a um número primo é de um em um milhão. Esse é o caso em que estamos tão sem sorte gerando os a's aleatóreos, que todos eles acabam sendo tolos. Se puder se debruçar sobre isso, é realmente muito importante para entender. Agora, podemos ver nosso teste em ação, com uma quantidade grande de tentativas, parece funcionar perfeitamente. Observe que no pior caso, que sabemos é quando fornecemos a nosso algoritmo um primo, ele fará o máximo de trabalho. O teste de Fermat é muito mais eficiente que o de divisão, especialmente porque o número de passos não escala com a entrada. E essa é uma diferença importante. Definimos um número de tentativas, e é isso. Não precisamos nos preocupar com nosso algoritmo rodando milhões e milhões de iterações como fizemos antes. Então, quero dizer, isso é matemática aplicada. Pegamos um padrão que alguém descobriu, e estamos economizando uma imensa quantidade de ciclos computacionais. Porem, há uma pequena falha, ou erro, nesse sistema. Você pode encontrá-lo?