Miller-Rabin primalitetstest beregner

Om denne beregner

Miller-Rabin-testen kontrollerer primalitet ved at skrive n − 1 som 2ˢ·d med d ulige og derefter teste, om en vidnebase a opfylder aᵈ ≡ 1 (mod n) eller a^(2ʳ·d) ≡ −1 (mod n) for et eller andet r < s. Et enkelt vidne giver kun et sandsynlighedsbaseret resultat, men at teste mod et lille, bevist sæt af faste vidnebaser (for eksempel 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) gør testen deterministisk for ethvert heltal under cirka 3,18 × 10²³ — langt ud over, hvad de fleste anvendelser nogensinde har brug for.

Kryptografer og softwareudviklere bruger netop denne slags test, når de genererer store primtalskandidater til RSA- eller Diffie-Hellman-nøgler, og studerende i datalogi bruger den til at se på virkelige tal, hvorfor Miller-Rabin skalerer så meget bedre end prøvedivision til at kontrollere, om et stort heltal er et primtal.