Miller–Rabin Witnesses

A worked example: n = 65, base a = 8

Consider the candidate n = 65 and base a = 8. We want to determine if 8 is a witness to the compositeness of 65.

1. First, decompose n - 1 into the form 2^s · d, where d is odd.
   65 - 1 = 64 = 2⁶ · 1. Thus, s = 6 and d = 1.
2. Compute the initial term of the chain: a^d mod n.
   8¹ mod 65 = 8.
3. Compute s-1 = 5 successive squarings modulo 65.
   • 8² = 64 ≡ -1 (mod 65).
   • Since we reached -1 (which is n-1), the condition is met. The rest of the sequence will just be 1.
   • 64² ≡ (-1)² = 1 (mod 65).
   • 1² = 1 (mod 65).
   • 1² = 1 (mod 65).
   • 1² = 1 (mod 65).
4. The full square chain is 8, 64, 1, 1, 1, 1. Because we encountered a 64 (which is n-1 or -1 mod n) before reaching the end of the squarings, the base 8 passes the test.
5. However, 65 is not prime (5 × 13). Therefore, 8 is a strong liar for 65, meaning 65 is a strong pseudoprime to base 8. A pass alone never says "Prime".

Interactive experiment

Open the Miller–Rabin Witnesses module to trace this calculation yourself.

1. Enter 65 in the "Candidate n" field.
2. Enter 8 in the "Base a" field.
3. Observe the Decomposition section: s becomes 6 and d becomes 1.
4. Check the Square chain: it computes the values 8 → 64 → 1 → 1 → 1 → 1.
5. Note the Status: it outputs Passes this base; not a primality proof.
6. 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.

Model limitations

This explorer focuses on a single chosen base to trace the exact integer arithmetic chain. It does not perform random sampling of multiple bases, and therefore it makes no statistical claims about the probability of primality. A "pass" means only that the specific chosen base failed to provide a witness to compositeness, not that the number is definitively prime. Small exact cases (n=2, 3) and even numbers are handled immediately as base-independent special cases. Candidate n is restricted to 2..5000 and Base a to 2..4999. For an odd candidate above 3, a valid test base must also lie in 2..n-2; modular exponentiation and squaring use exact BigInt arithmetic.

References

The mathematical properties and conditions for strong pseudoprimes and Miller-Rabin witnesses are detailed in algorithmic reference materials:

• CP-Algorithms: Primality tests — Explains the Miller–Rabin decomposition, witness/pass conditions and strong liars.