Teste de primalidade aleatório (aquecimento)

RKA10GM Primeiro, vamos introduzir alguns conceitos para este novo tipo de algoritmo randômico que aceita uma entrada "n". Se ele é primo, nosso algoritmo retorna como primo com 100% de certeza, e ele nunca irá rotular esse número como composto. No entanto, se ele é composto, existirá uma pequena chance do erro "e" ser classificado como primo. Caso contrário, haverá 1-, essa pequena probabilidade de erro, de que ele seja corretamente identificado como composto. Retiraremos de um universo de números inteiros um inteiro "n" e o colocaremos na nossa máquina antiga, que trabalha com o método de teste de divisão, no qual basicamente testamos todos os valores de 1 até a raiz quadrada de "n", para saber se algum deles divide "n". O ideal seria testar apenas os primos para economizar tempo. Se "a" divide "n", então sabemos que "n" é um número composto, pois acabamos de achar uma prova disso. Se não divide, então não temos certeza. Temos que incrementar "a" e testar de novo. Uma vez que esgotarmos todos os valores possíveis, poderemos dizer que "n" é primo se não tivermos encontrado nenhum divisor. Mas para que tanto esforço? Podemos pegar alguns inteiros aleatoriamente e realizar alguns testes de divisibilidade, que podem ser entendidos como perguntas aleatórias. Uma vez que sabemos que se algum número "n" é composto, ele deve ter alguns divisores espalhados por aí. No mínimo, ele tem um divisor e pode, provavelmente, ter vários. De qualquer forma, escolhemos um inteiro aleatório "a", entre 1 e a raiz quadrada de "n". Então, apenas checamos se "a" divide "n". Como antes, se "a" divide "n", então sabemos, com certeza, que "n" é composto, pois achamos uma prova. Se não acharmos, então não aprendemos muito além de que ele pode ser primo. Por segurança, poderíamos gerar mais alguns "a" aleatórios e continuar testando. Talvez, depois de 100 mil "a" gerados, poderemos dizer, com alguma certeza, que provavelmente é um primo. Digamos 99,9%, por exemplo. Isso é semelhante ao exemplo do jogo de probabilidade condicional. Na versão mais simples, tentamos adivinhar se a moeda era justa ou viciada. No caso, coroa é como achar um divisor, uma prova que a moeda é justa. Cara é o caso no qual vamos desejar que a moeda seja jogada novamente. Depois de cinco caras, teremos mais de 90% de certeza. Então, vamos parar e dizer que achamos que a moeda é viciada. Aqui está um programa que preparei e que compara nosso teste antigo, de encontrar primos, com este novo. Ele se baseia no programa Trial Division Speed Leader, do criador Dino, cujo link está no cabeçalho do programa. Note que a variável numTrials é o número de tentativas aleatórias. Vamos começar com um valor pequeno, por exemplo, 3. Note também um pequeno valor de entrada. Se ele for primo, o algoritmo de divisão randômica sempre responderá "primo". Mas quando a entrada é composta, vemos que esse algoritmo pode se enganar e identificá-la incorretamente como primo. Contudo, podemos corrigir isso aumentando o número de tentativas e a probabilidade de erro diminui. Agora, veremos que as respostas casam mais ou menos e à medida que se testam entradas maiores, o erro cresce novamente. Então, temos que aumentar o número de testes de acordo com o tamanho da entrada. Dessa forma, as saídas dos dois algoritmos parecem idênticas. Mas para grandes valores de entrada, precisamos de muitos testes aleatórios, para que a saída seja precisa. Então, não diminuímos a quantidade de passos necessária, e o algoritmo antigo ainda parece melhor. Isso ocorre porque a taxa de erro do teste de divisão é muito alta, mas estamos no caminho certo. Então, precisamos de outro teste. Precisamos de uma equação que seja rápida de calcular e possa provar se um número é composto. Ela deve acertar não só o inteiro "n", mas também o inteiro aleatório "a". Basta usá-la como um teste, assim como foi feito com a divisão.