🔢 Miller-Rabin Primality Test

⚙️ Decompose n−1

Write n−1 = 2ˢ·d (d odd). This exposes the 2-adic structure needed for squaring.

—

🎯 Witness Test

For witness a: compute x = aᵈ mod n. Square up to s times. Must hit 1 or n−1 at the right step — otherwise → COMPOSITE.

📊 Accuracy

Each round catches composites with prob ≥ 3/4 (Rabin). After k=5 rounds: error ≤ 4⁻⁵ < 0.1%. Used in RSA key generation.