Llogaritës i testit të thjeshtësisë Miller-Rabin

Rreth kësaj llogaritëseje

Testi Miller-Rabin kontrollon thjeshtësinë e një numri duke shkruar n − 1 si 2ˢ·d me d tek, pastaj duke provuar nëse një bazë dëshmitare a plotëson aᵈ ≡ 1 (mod n) ose a^(2ʳ·d) ≡ −1 (mod n) për ndonjë r < s. Një dëshmitar i vetëm jep vetëm një rezultat probabilistik, por testimi me një grup të vogël të provuar bazash dëshmitare të fiksuara (për shembull 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) e bën testin deterministik për çdo numër të plotë nën afërsisht 3,18 × 10²³ — shumë përtej asaj që u nevojitet shumicës së aplikacioneve.

Kriptografët dhe zhvilluesit e softuerit përdorin pikërisht këtë lloj testi kur gjenerojnë kandidatë të mëdhenj për numra të thjeshtë për çelësat RSA ose Diffie-Hellman, ndërsa studentët e shkencave kompjuterike e përdorin për të parë, mbi numra realë, pse Miller-Rabin shkallëzohet shumë më mirë se pjesëtimi me prova kur kontrollohet nëse një numër i plotë i madh është i thjeshtë.