Calculadora do Teste de Primalidade de Miller-Rabin

Sobre esta calculadora

O teste de Miller-Rabin verifica a primalidade escrevendo n − 1 como 2ˢ·d com d ímpar e, em seguida, testando se uma base testemunha a satisfaz aᵈ ≡ 1 (mod n) ou a^(2ʳ·d) ≡ −1 (mod n) para algum r < s. Uma única testemunha dá apenas um resultado probabilístico, mas testar contra um pequeno conjunto comprovado de bases testemunha fixas (por exemplo 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) torna o teste determinístico para todo inteiro abaixo de aproximadamente 3,18 × 10²³ — muito além do que a maioria das aplicações jamais precisa.

Criptógrafos e desenvolvedores de software usam exatamente esse tipo de teste ao gerar candidatos a números primos grandes para chaves RSA ou Diffie-Hellman, e estudantes de ciência da computação o usam para ver, em números reais, por que o Miller-Rabin escala muito melhor do que a divisão por tentativas para verificar se um inteiro grande é primo.