Verificador de Primalidade

O verificador de primalidade informa se um número inteiro é primo e — ao contrário da maioria das calculadoras on-line — mostra o algoritmo real que provou isso, não uma tabela de pesquisa em cache. Digite qualquer número inteiro, positivo ou negativo, pequeno ou enorme, e a ferramenta decide qual algoritmo real executar com base em seu tamanho.

Para números abaixo de 10¹² (um trilhão), ele executa uma divisão experimental genuína: começando em 2, ele tenta todos os candidatos inteiros até o piso de √n como um possível divisor, parando no momento em que um divide uniformemente (composto) ou confirmando que nenhum o faz, uma vez que todos os candidatos até √n tenham sido verificados (primo). Para grandes contagens de candidatos, o rastreamento mostrado é limitado aos primeiros ~18 tentados mais o final, com uma nota honesta sobre quantos foram ignorados na exibição - mas cada candidato ainda é realmente verificado pelo código, nenhum é ignorado no cálculo.

Para números iguais ou superiores a esse limite - a faixa de tamanho usada na criptografia - a divisão experimental levaria muito tempo, então a ferramenta muda para o teste de primalidade de Miller-Rabin com um conjunto fixo e determinístico de 13 testemunhas principais (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Este conjunto exato de testemunhas é um resultado bem conhecido: não tem falsos positivos para qualquer n abaixo de 3.317.044.064.679.887.385.961.981 (cerca de 3,3 × 10²⁴), um limite estabelecido por verificação computacional (ver Sorenson & Webster, 2015, e a tabela de testemunhas determinísticas amplamente reproduzida à qual pertence). Acima desse limite, o mesmo teste ainda é executado, mas a ferramenta diz honestamente que a garantia se torna uma garantia probabilística extremamente forte, em vez de uma certeza matemática.

O traço de Miller-Rabin escreve n - 1 = 2ˢ × d com d ímpar, depois percorre a exponenciação modular BigInt real - quadrado e multiplicado, reduzindo o módulo n a cada passo para que os números nunca explodam - pouco a pouco para a primeira testemunha, e relata o veredicto de cada testemunha, incluindo qual testemunha prova a composição se o número não for primo. Tudo é executado localmente no seu navegador: nenhum servidor, nenhuma API externa, nenhum dado sai do seu dispositivo.