Miller-Rabin Primality Test
Miller-Rabin is a probabilistic primality test: writing n-1=2^s*d, it checks a^d≡1 or some a^(2^r*d)≡-1 (mod n), with a false-positive probability of at most 1/4 per round.
Purpose
To test primality efficiently and probabilistically, used for RSA large-prime generation.
Mechanism
For n-1=2^s*d, pick a random a∈[2,n-2] and compute x=a^d mod n. If x=1 or n-1, n is probably prime. Otherwise square up to s-1 times; hitting n-1 means probably prime, otherwise n is definitely composite. After k rounds the error probability is at most 4^(-k).
Use cases
- RSA prime generation
- Primality testing
- Cryptography implementations
Related tools
Prime Checker
Prime Checker — pure client-side tool. Privacy-first, no server round-trip. TOOL
Prime Generator
Prime Generator — pure client-side tool. Privacy-first, no server round-trip. TOOL
Miller Rabin Primality Test
Miller Rabin Primality Test — pure client-side tool. Privacy-first, no server round-trip. TOOL