Miller-Rabin priemtest calculator

Over deze rekenmachine

De Miller-Rabin-test onderzoekt of een getal priem is door n − 1 te schrijven als 2ˢ·d met d oneven en vervolgens na te gaan of een getuigegrondtal a voldoet aan aᵈ ≡ 1 (mod n) of a^(2ʳ·d) ≡ −1 (mod n) voor een of andere r < s. Eén enkel getuigegrondtal geeft slechts een kansuitkomst, maar toetsing met een kleine, bewezen vaste verzameling getuigegrondtallen (bijvoorbeeld 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) maakt de test deterministisch voor elk geheel getal onder ongeveer 3,18 × 10²³ — veel meer dan de meeste toepassingen ooit nodig hebben.

Cryptografen en softwareontwikkelaars gebruiken precies zo'n test bij het genereren van grote priemkandidaten voor RSA- of Diffie-Hellman-sleutels, en informaticastudenten gebruiken hem om aan de hand van echte getallen te zien waarom Miller-Rabin zoveel beter schaalt dan proefdeling bij het controleren of een groot geheel getal priem is.