Miller-Rabin Primality Test Visualizer

Miller-Rabin Primality Test Visualizer

Test a Number for Primality

The Miller-Rabin test is a probabilistic algorithm to determine if a number is probably prime.

Number to Test:

Test Iterations (k): (More iterations = more accurate)

How the Miller-Rabin Test Works

1. Decompose n-1 into d × 2^s
2. For each iteration:
   1. Pick a random base a between 2 and n-2
   2. Compute x = a^d mod n
   3. If x ≡ 1 or x ≡ n-1, continue to next iteration
   4. Otherwise, square x up to s-1 times
   5. If none of these squares ≡ n-1, then n is composite
3. If all iterations pass, n is probably prime