Miller-Rabin-alkulukutestin Laskuri

Tietoa tästä laskurista

Miller–Rabin-testi tarkistaa alkulukuisuuden kirjoittamalla n − 1 muotoon 2ˢ·d, missä d on pariton, ja testaamalla, toteuttaako todistajakanta a ehdon aᵈ ≡ 1 (mod n) tai a^(2ʳ·d) ≡ −1 (mod n) jollakin r < s. Yksittäinen todistaja antaa vain todennäköisyyspohjaisen tuloksen, mutta testaaminen pienellä, todistetulla kiinteiden todistajakantojen joukolla (esimerkiksi 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) tekee testistä deterministisen jokaiselle kokonaisluvulle, joka on alle noin 3,18 × 10²³ – paljon enemmän kuin useimmat sovellukset koskaan tarvitsevat.

Kryptografit ja ohjelmistokehittäjät käyttävät juuri tällaista testiä luodessaan suuria alkulukuehdokkaita RSA- tai Diffie–Hellman-avaimille, ja tietojenkäsittelytieteen opiskelijat käyttävät sitä nähdäkseen todellisilla luvuilla, miksi Miller–Rabin skaalautuu paljon paremmin kuin kokeilujako suuren kokonaisluvun alkuluvuksi tarkistamisessa.