Miller–Rabin Primality Test

Number to Test

n (odd) 561

Test Parameters

Rounds (k) — random bases 4

Press "Run" to test n.

Live State

n − 1 = 2^r · d

Round / base a

–

Step (squaring)

–

Current xᵢ mod n

–

Error bound after k

≤ 4⁻ᵏ

How it works

To test odd n > 2, write n − 1 = 2^r·d with d odd. For a random base a ∈ [2, n − 2], compute the squaring chain:

x₀ = a^d mod n
x₁ = x₀² mod n
x₂ = x₁² mod n
  ...
x_(r-1) = x_(r-2)² mod n

a is not a witness to compositeness (n "passes" this round) if x₀ = 1, or if xᵢ = n − 1 for some i < r. Otherwise a proves n composite outright — this follows from the fact that in a field ℤ/nℤ with n prime, the only square roots of 1 are ±1, so any other square root caught mid-chain betrays a composite modulus.

Each random base has at most 1/4 probability of falsely passing a composite n, so after k independent rounds the false-positive probability is at most 4^−k — with k = 4 that is already ≤ 1/256, and it drops fast from there. This is exactly the primality test used to generate the large primes inside RSA key pairs. Try loading 561: it is a Carmichael number that fools the weaker Fermat test for almost every base, yet Miller–Rabin catches it because the squaring chain exposes a nontrivial square root of 1.

n slider / presets — pick the odd number under test; "Random composite" occasionally lands on a prime by chance of construction, "Random prime" always yields a true prime.
Rounds (k) — how many independent random bases to try before declaring n "probably prime".
Run test — animates each round's squaring chain spiraling around the mod-n ring; a green trail means that base passed, red means it caught n as composite.

Residue ring (mod n) Round passed (probable prime) Witness found (composite)

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.