Formula Used
The Miller-Rabin primality test is a probabilistic algorithm which confirms whether a given number is likely prime. Given an odd integer $n > 2$, we write $n - 1 = 2^s \cdot d$, where $d$ is odd. For a chosen base $a$ ($2 \le a \le n-2$), the algorithm checks if either:
- $a^d \equiv 1 \pmod n$
- $a^{2^r \cdot d} \equiv -1 \pmod n$ for some $0 \le r < s$
If neither condition holds, then $n$ is a composite number, and $a$ is a strong witness for compositeness.
How to Use This Calculator
- Enter the target numeric value into the primary input box.
- Select your preferred test mode strategy from the dropdown menu.
- Adjust the iteration rounds or input custom base parameters if necessary.
- Click the run button to process the advanced modular calculations instantly.
Understanding Probabilistic Primality Testing
In modern computer science and cryptographic protocols like RSA, validating large prime numbers forms the bedrock of secure data transmission. Traditional trial division quickly becomes computationally infeasible as integer sizes scale into hundreds or thousands of digits. The Miller-Rabin primality test offers an efficient probabilistic alternative, capable of determining primality with high mathematical confidence in polynomial time.
Unlike deterministic checks that exhaustively divide every potential factor, the Miller-Rabin algorithm relies on modular exponentiation properties derived from Fermat's Little Theorem. By evaluating multiple random bases $a$, the probability of a composite number falsely passing as prime decreases exponentially with each iteration round. For instance, executing 10 independent random rounds reduces the error probability to less than $4^{-10}$, making it practically foolproof for real-world cryptographic applications.
Carmichael Numbers and Challenges
A classic hurdle in elementary primality testing is the existence of Carmichael numbers—composite numbers that satisfy Fermat's Little Theorem for all coprime bases, tricking simpler pseudoprime tests. Carmichael numbers like 561 successfully masquerade as primes under basic tests, but the Miller-Rabin algorithm successfully exposes their composite nature by checking square roots of unity modulo $n$. This robust mechanism guarantees that composite numbers are reliably flagged.