MillerRabin

Miller-Rabin is a probabilistic primality test used to determine whether a given integer is prime. It is commonly referred to as the Miller–Rabin test, named after Gary L. Miller and Michael O. Rabin, who developed and refined it in the late 20th century. The algorithm tests numbers for primality by assessing whether they are strong probable primes to certain bases, providing a controllable trade-off between efficiency and error probability.

The test operates on odd integers n > 2. Write n − 1 as d · 2^s with d odd. For each chosen base a in a specified range (2 ≤ a ≤ n − 2), compute x = a^d mod n. If x is 1 or n − 1, n passes this base. Otherwise, repeatedly square x modulo n up to s − 1 times; if any squaring yields n − 1, n passes this base. If none do, n is declared composite. Repeating the test with multiple bases reduces the chance that a composite number passes as a prime; for a random base, a composite n has at most a 1/4 probability of passing a single round, so k rounds yield a probability of at most (1/4)^k of error.

Deterministic variants exist for numbers below certain bounds, using fixed sets of bases to guarantee primality within those ranges. In practice, Miller–Rabin is widely used in cryptography and prime generation due to its speed and simplicity, often combined with other primality checks or used with a small, fixed number of bases to achieve a desired reliability.

Overall, Miller-Rabin provides a practical balance between accuracy and performance, making it a standard tool in primality testing for large integers and cryptographic applications.