Kalkulator Miller-Rabinovog testa prostosti

O ovom kalkulatoru

Miller-Rabinov test provjerava prostost tako da n − 1 zapiše kao 2ˢ·d uz neparan d, a zatim ispituje zadovoljava li svjedok baza a uvjet aᵈ ≡ 1 (mod n) ili a^(2ʳ·d) ≡ −1 (mod n) za neki r < s. Jedan svjedok daje samo vjerojatnosni rezultat, ali testiranje prema maloj, dokazanoj skupini fiksnih baza svjedoka (primjerice 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) čini test determinističkim za svaki cijeli broj manji od otprilike 3,18 × 10²³ — daleko više od onoga što većina primjena ikada treba.

Kriptografi i razvojni programeri koriste upravo ovakav test pri generiranju velikih kandidata za proste brojeve za RSA ili Diffie-Hellman ključeve, a studenti računarstva ga koriste da na stvarnim brojevima vide zašto se Miller-Rabin mnogo bolje skalira od probnog dijeljenja pri provjeri je li velik cijeli broj prost.