A probabilistic algorithm that tests whether an odd integer n is probably prime by performing one or more strong probable-prime checks to random (or chosen) bases using modular exponentiation and squaring rules.

Principle

Write n-1 = 2^s * d with d odd; for a base a, compute a^d mod n and successive squarings; if none of these values equal 1 or n-1 in the required pattern, n is composite. Repeating with independent bases reduces the error probability exponentially.

Demonstration

Test n=561 with base a=2: compute 2^{d} mod 561 and its squares; the test exposes a witness to compositeness (561 is a Carmichael number), so Miller–Rabin detects it as composite for some bases but may be a strong probable prime for others — hence multiple bases are used.

Misapplication

Treating a Miller–Rabin 'probable prime' outcome as an absolute proof of primality without sufficient bases, or using too few rounds in cryptographic contexts where the small residual error can be exploited.

Consequence

Offers a fast, easily tunable probabilistic primality test: with a suitable choice/number of bases the probability of a composite passing all tests becomes negligibly small; for certain size ranges fixed bases give deterministic results.

Reversal

Use deterministic primality proofs (e.g., certificate-producing algorithms) or full factorization to obtain certainty instead of probabilistic assurance.

Boundary

Only a probabilistic test: it asserts 'probable prime' or 'composite' with one-sided error (composites may pass); deterministic guarantees require extra rounds, chosen bases for bounded ranges, or different algorithms.

Semantic Tension

Competes with deterministic and certificate-based primality tests: Miller–Rabin is far faster for large numbers and sufficient for most practical uses, but its probabilistic nature contrasts with provable primality algorithms.

Synthesis

Miller–Rabin is a rapid randomized filter based on modular exponentiation and squaring that, with repeated independent bases, drives the probability of erroneously classifying a composite as prime down to negligible levels while remaining computationally cheap.