Miller-Rabin prímteszt kalkulátor

Erről a kalkulátorról

A Miller–Rabin-teszt úgy ellenőrzi a prímséget, hogy n − 1-et felírja 2ˢ·d alakban, ahol d páratlan, majd megvizsgálja, hogy egy a tanúalap kielégíti-e az aᵈ ≡ 1 (mod n) vagy az a^(2ʳ·d) ≡ −1 (mod n) feltételt valamely r < s esetén. Egyetlen tanú csak valószínűségi eredményt ad, de ha egy kicsi, bizonyítottan elegendő, rögzített tanúalap-halmazzal (például 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) tesztelünk, a teszt determinisztikussá válik minden nagyjából 3,18 × 10²³ alatti egész számra – ami messze meghaladja azt, amire a legtöbb alkalmazásnak valaha szüksége van.

A kriptográfusok és a szoftverfejlesztők pontosan ilyen tesztet használnak RSA- vagy Diffie–Hellman-kulcsok nagy prímjelöltjeinek generálásakor, az informatikát tanuló diákok pedig ezzel látják valódi számokon, miért skálázódik a Miller–Rabin sokkal jobban, mint a próbaosztás egy nagy egész szám prímségének ellenőrzésére.