Miller-Rabin Primality Test Calculator

About this calculator

The Miller-Rabin test checks primality by writing n − 1 as 2ˢ·d with d odd, then testing whether a witness base a satisfies aᵈ ≡ 1 (mod n) or a^(2ʳ·d) ≡ −1 (mod n) for some r < s. A single witness only gives a probabilistic result, but testing against a small, proven set of fixed witness bases (for example 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) makes the test deterministic for every integer below roughly 3.3 × 10²⁴ — far beyond what most applications ever need.

Cryptographers and software developers use exactly this kind of test when generating large prime candidates for RSA or Diffie-Hellman keys, and computer science students use it to see, on real numbers, why Miller-Rabin scales so much better than trial division for checking whether a big integer is prime.