Miller–Rabin Witness Density & Convergence (2D)

Scan Range (odd n)

Start 15

End 615

Highlighted n

561

MR witness fraction

–

Fermat witness fraction*

–

Theorem check (composite ⇒ MR fraction ≥ 0.75)

–

Monte Carlo Convergence

Rounds k (max tested) 6

Trials per k 4000

Composite pool size

Worst k tested

–

Legend

Prime (baseline, 0 witnesses) Composite — MR witness fraction (bar height) Highlighted n 0.75 theorem threshold

What this 2D scan adds

The 3D scene animates one random round of the Miller-Rabin test spiraling around a residue ring. This 2D companion instead brute-force computes, for every odd n in the chosen range, the exact fraction of bases a ∈ [2, n−2] that are true witnesses to compositeness:

witness(n,a) = true unless a^d ≡ 1 (mod n)
                          or a^(d·2^i) ≡ n−1 (mod n) for some i < r
fraction(n) = #{a : witness(n,a)} / (n − 3)

The classical theorem guarantees fraction(n) ≥ 3/4 for every composite n (with a handful of tiny exceptions below n=49) — this scan draws that bound as a real, measured curve instead of asserting it. It also separates a Carmichael number's two faces: restricted to bases coprime to n, the Fermat test's witness fraction collapses near zero (that's the whole trick a Carmichael number pulls), while the Miller-Rabin fraction over the same n stays ≥ 0.75 — the squaring chain exposes a nontrivial square root of 1 that Fermat's test never looks for.

The Monte Carlo panel then closes the loop: it samples the composite numbers actually found in the scan, runs k independent random-base rounds many times, and measures the real false-positive rate — how often a genuinely composite n slips through as "probably prime" — directly against the theoretical 4^−k ceiling.

Scan Range — the window of odd numbers to brute-force; wider ranges take a little longer to scan (all math runs synchronously, so very large ranges will pause the UI briefly).
Jump to 561 — loads the classic Carmichael number and highlights it on the scan.
Monte Carlo — draws n uniformly from the composite pool of the last scan, runs k rounds with fresh random bases each trial, and tallies how often all k rounds falsely pass.

*Fermat witness fraction is computed only over bases coprime to n — the actual scope of Fermat's little theorem and of the Carmichael-number guarantee.

MR witness-fraction scan (brute force, exact)

⚠ Couldn't start the canvas2D canvas context failed to initialize. Reload the page.

log₁₀(false-positive rate) vs rounds k — empirical vs 4⁻ᵏ bound