##  [Miller–Rabin Primality Test](/miller-rabin-primality-test-0) 

 Definition

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

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

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

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

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

Reversal

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

 

 

 

 

 





## Boundary

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

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

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.