Calcolatore del test di primalità di Miller-Rabin

Informazioni su questo calcolatore

Il test di Miller-Rabin verifica la primalità scrivendo n − 1 come 2ˢ·d con d dispari, poi controllando se una base testimone a soddisfa aᵈ ≡ 1 (mod n) oppure a^(2ʳ·d) ≡ −1 (mod n) per qualche r < s. Un singolo testimone dà solo un risultato probabilistico, ma verificare un piccolo insieme dimostrato di basi testimone fisse (per esempio 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) rende il test deterministico per ogni numero intero inferiore a circa 3,18 × 10²³, ben oltre ciò di cui la maggior parte delle applicazioni ha mai bisogno.

Crittografi e sviluppatori di software usano proprio questo tipo di test quando generano grandi candidati primi per le chiavi RSA o Diffie-Hellman, e gli studenti di informatica lo usano per vedere, su numeri reali, perché Miller-Rabin scala molto meglio della divisione per tentativi nel verificare se un grande numero intero è primo.