Miller–Rabin Witnesses
Inspect a modular squaring chain to distinguish a compositeness witness from a base that merely passes.
Free theory articleInspect a modular squaring chain to distinguish a compositeness witness from a base that merely passes.
Concept & interpretation
The Miller–Rabin test is a probabilistic primality test that relies on properties of strong pseudoprimes. Instead of definitively proving primality, it seeks a "witness" to compositeness. If no witness is found after many random bases, the candidate is likely prime.
Interactive experiment
Open the Miller–Rabin Witnesses module to trace this calculation yourself.
- Enter 65 in the "Candidate n" field.
- Enter 8 in the "Base a" field.
- Observe the Decomposition section: s becomes 6 and d becomes 1.
- Check the Square chain: it computes the values 8 → 64 → 1 → 1 → 1 → 1.
- Note the Status: it outputs Passes this base; not a primality proof.
- Now change the base to 2. The chain becomes 2 → 4 → 16 → 61 → 16 → 61. Neither 1 nor 64 (-1) appears as required, so it correctly reports Composite witness.