Calculadora do Test de Primalidade de Miller-Rabin

Sobre esta calculadora

O test de Miller-Rabin comproba a primalidade escribindo n − 1 como 2ˢ·d con d impar e probando despois se unha base testemuña a cumpre aᵈ ≡ 1 (mod n) ou a^(2ʳ·d) ≡ −1 (mod n) para algún r < s. Unha soa testemuña só dá un resultado probabilístico, pero probar cun conxunto pequeno e demostrado de bases testemuña fixas (por exemplo 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) fai que o test sexa determinista para todo enteiro inferior a aproximadamente 3,18 × 10²³ — moi por riba do que a maioría das aplicacións necesitan nunca.

Os criptógrafos e os desenvolvedores de software empregan exactamente este tipo de test ao xerar candidatos a números primos grandes para claves RSA ou Diffie-Hellman, e o alumnado de informática emprega isto para ver, con números reais, por que Miller-Rabin escala moito mellor que a división por tentativas para comprobar se un enteiro grande é primo.