Calculator ng Miller-Rabin Primality Test

Tungkol sa calculator na ito

Sinusuri ng Miller-Rabin test ang pagiging prime sa pamamagitan ng pagsulat sa n − 1 bilang 2ˢ·d na ang d ay odd, saka sinusubukan kung ang isang witness base na a ay tumutugon sa aᵈ ≡ 1 (mod n) o a^(2ʳ·d) ≡ −1 (mod n) para sa ilang r < s. Ang iisang witness ay nagbibigay lamang ng probabilistikong resulta, ngunit ang pagsubok laban sa maliit at napatunayang set ng mga nakapirming witness base (halimbawa 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) ay ginagawang deterministiko ang test para sa bawat integer na mas mababa sa humigit-kumulang 3.18 × 10²³ — higit pa sa kailangan ng karamihan ng aplikasyon.

Ginagamit ng mga cryptographer at software developer ang eksaktong ganitong test sa paglikha ng malalaking prime candidate para sa mga RSA o Diffie-Hellman key, at ginagamit ng mga mag-aaral ng computer science ito upang makita, sa totoong mga numero, kung bakit mas mahusay ang scaling ng Miller-Rabin kaysa sa trial division sa pagsuri kung prime ang malaking integer.