Introduction
Is that 600-digit number prime? Factoring it to find out would take forever, but the Miller-Rabin primality test can tell you with overwhelming probability in seconds. This tool runs the Miller-Rabin test on any integer using BigInt arithmetic, showing you the per-witness trace: how it writes n-1 as 2^r * d, then checks a^d, a^(2d), a^(4d), and so on modulo n. You see exactly which witnesses pass, which fail, and why. Paste a number, pick how many witnesses to test, and watch the test run step by step in your browser.
What this tool does
- Run the Miller-Rabin primality test on any positive integer using BigInt arithmetic, with no upper bound on input size beyond your browser's memory
- Show the per-witness trace: factor n-1 = 2^r * d, then compute a^d mod n, a^(2d) mod n, a^(4d) mod n, through a^(2^(r-1) * d) mod n, marking each as pass or fail
- Test with the first k primes (2, 3, 5, 7, 11, 13, ...) as witnesses, or with random bases, with k configurable from 1 to 40
- Report deterministic results for n < 3,317,044,064,679,887,385,961,981 using the first 13 prime witnesses (Sorenson and Webster 2017), so there is no probabilistic uncertainty for numbers below that bound
- Detect composites instantly for small factors and display the specific witness that proved compositeness
- Run entirely client-side with no network calls, so you can test sensitive numbers privately
How this tool works
The tool takes an integer n and a witness count k as input. If n is even, small, or obviously composite, it reports that immediately. Otherwise it writes n-1 = 2^r * d by repeatedly dividing by 2 while d is even, counting the factors of 2 as r.
For each witness a (the first k primes by default, or random bases if you choose), the tool computes x = a^d mod n using fast modular exponentiation (square-and-multiply, O(log d) multiplications). If x is 1 or n-1, this witness says "probably prime" and the tool moves to the next witness. Otherwise it squares x repeatedly, up to r-1 times, computing a^(2d), a^(4d), ..., a^(2^(r-1) * d) mod n. If any of these equals n-1, the witness passes. If any equals 1 without having first hit n-1, or if none of them equals n-1, the witness proves n is composite.
The trace panel shows each witness with its computed sequence. For example, testing n = 561 (a Carmichael number) with witness a = 2: n-1 = 560 = 2^4 * 35, so r = 4, d = 35. The tool computes 2^35 mod 561 = 263, then 263^2 mod 561 = 166, then 166^2 mod 561 = 67, then 67^2 mod 561 = 1. Since we hit 1 without ever seeing 560 (n-1), the witness proves 561 is composite.
For numbers below 3.3 * 10^24, the tool uses the first 13 primes (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41) and reports a deterministic result with no probability qualifier. For larger numbers, it reports the probability of a false positive, which is at most 4^(-k) after k witnesses.
How the Miller-Rabin test works (Rabin 1980)
The Miller-Rabin test was proposed by Gary L. Miller in 1976 as a deterministic test conditional on the unproven Generalized Riemann Hypothesis (GRH), then made practical as a probabilistic test by Michael O. Rabin in 1980 (Rabin 1980). Rabin proved that for any composite n, at least 3/4 of bases a in [2, n-2] are witnesses to compositeness. So after k independent random witnesses, the probability of a false "prime" is at most 4^(-k). With k = 40, that is less than 10^(-24).
The test relies on a property of primes. If n is prime and n-1 = 2^r * d with d odd, then for any a not divisible by n, either a^d = 1 mod n, or a^(2^j * d) = n-1 mod n for some j in [0, r-1]. This follows from the fact that the only square roots of 1 modulo a prime are 1 and -1. A composite number that fails this for some base a is caught.
In 2017, Sorenson and Webster proved that the first 13 prime witnesses (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41) are sufficient for a deterministic result for all n < 3,317,044,064,679,887,385,961,981 (about 3.3 * 10^24). This extends earlier work by Jaeschke (1993) and Zhang and Tang (2003). For practical purposes, any number below that bound can be tested deterministically in milliseconds.
The Miller-Rabin test is used in OpenSSL's `BN_is_prime_fasttest_ex`, Go's `crypto/rand.Prime` (which generates primes by testing random candidates with Miller-Rabin), and most JWT and RSA key generation libraries. It is the standard primality test in production cryptography because it is fast, simple, and its error bound is well understood.
How to use this tool
- Enter the number n you want to test in the input field. The tool accepts decimal or hex (prefix with 0x)
- Choose the number of witnesses. The default is 13, which gives a deterministic result for n < 3.3 * 10^24. For larger numbers, use 20 to 40 for high confidence
- Choose witness type: first k primes (recommended, deterministic for small n) or k random bases
- Click Test. The tool computes n-1 = 2^r * d and runs each witness
- Read the result: "prime" (all witnesses passed and n is below the deterministic bound), "probably prime" (all witnesses passed but n is large), or "composite" (a witness failed)
- Expand the per-witness trace to see the sequence a^d, a^(2d), ..., a^(2^(r-1) * d) mod n for each witness, with pass or fail marked
- If composite, note which witness proved it and at which step (the tool highlights the failing step)
Real-world examples
Testing a Carmichael number
Input: n = 561. The tool writes 560 = 2^4 * 35, so r = 4, d = 35. Witness a = 2: 2^35 mod 561 = 263, 263^2 mod 561 = 166, 166^2 mod 561 = 67, 67^2 mod 561 = 1. Since we reached 1 without seeing 560, n is composite. 561 is the smallest Carmichael number, which passes Fermat's test for every base coprime to it but fails Miller-Rabin.
Confirming a large prime
Input: n = 2^1279 - 1 (a Mersenne prime, 386 digits). The tool writes n-1 = 2 * ((n-1)/2) with d odd. All 13 prime witnesses pass: for each a, either a^d mod n is 1 or n-1, or some a^(2^j * d) mod n hits n-1. The result is "prime" deterministically. This takes a few seconds due to the size of the modular exponentiations.
A composite that fools a single witness
Input: n = 25326001, witness count 1, witness a = 2. The test passes (2 is not a witness for this number). But with witness a = 3, the test fails and proves compositeness. This shows why a single witness is not enough: some composites have many non-witnesses. Using the first 13 primes avoids this problem for n < 3.3 * 10^24.
Comparison with similar methods
| Method | Complexity | Typical use |
|---|---|---|
| Miller-Rabin (probabilistic) | O(k * log^3 n) for k witnesses | Production key generation, OpenSSL, Go crypto |
| Miller-Rabin (deterministic, 13 primes) | O(13 * log^3 n) | Deterministic for n < 3.3 * 10^24 (Sorenson-Webster 2017) |
| AKS primality test | O(log^6 n) deterministic | Theoretical, too slow for practice |
| Fermat test | O(log^3 n) per witness | Weak, fooled by Carmichael numbers |
| Trial division | O(sqrt(n)) | Small numbers only, impractical for large n |
Limitations or considerations
The Miller-Rabin test is probabilistic for numbers above 3.3 * 10^24. With k witnesses, the probability of a false positive is at most 4^(-k). With k = 40, this is about 10^(-24), which is negligible for any practical purpose, but it is not zero. Only the AKS test (Agrawal-Kayal-Saxena, 2002) is deterministic and unconditional for all n, but it is far too slow for practical use.
The tool uses BigInt arithmetic, which is slower than native big-integer libraries like GMP. Testing a 4096-bit number with 40 witnesses takes a few seconds. For numbers with thousands of digits, each modular exponentiation involves millions of BigInt multiplications, so expect longer run times.
The tool does not generate primes. To generate a random prime, you would pick random candidates and test each with Miller-Rabin until one passes. Use the Prime Number Generator for that, which does exactly this.
The tool does not prove primality with a certificate. For a primality proof (not just a test), you would use the Pratt certificate or the ECPP (Elliptic Curve Primality Proving) algorithm, which this tool does not implement.
Frequently asked questions
Is Miller-Rabin deterministic or probabilistic?
Both, depending on the number size. For n < 3,317,044,064,679,887,385,961,981 (about 3.3 * 10^24), the first 13 primes as witnesses give a deterministic result (Sorenson and Webster 2017). For larger n, the test is probabilistic with error probability at most 4^(-k) after k witnesses.
What is a Carmichael number and why does it matter?
A Carmichael number is a composite n that passes Fermat's primality test (a^(n-1) = 1 mod n) for every a coprime to n. The smallest is 561. Carmichael numbers show why the Fermat test is unreliable. Miller-Rabin is stronger: it catches Carmichael numbers because it checks intermediate squarings, not just the final exponent.
How many witnesses should I use?
For n < 3.3 * 10^24, 13 witnesses (the first 13 primes) give a deterministic result. For larger n, use 20 for general use (error < 10^(-12)) or 40 for high-assurance applications (error < 10^(-24)). OpenSSL defaults to 64 rounds for key generation. More witnesses cost more time but reduce error exponentially.
Why does the tool use the first k primes instead of random bases?
Using the first k primes (2, 3, 5, 7, ...) gives deterministic results for small n, which random bases cannot. For large n, prime bases are slightly more effective than random bases on average. The tool also supports random bases if you prefer them.
What is the difference between Miller-Rabin and the AKS test?
Miller-Rabin is probabilistic (for large n) but fast, running in O(k * log^3 n). AKS (Agrawal-Kayal-Saxena, 2002) is deterministic and unconditional for all n, but runs in O(log^6 n) and is far slower in practice. No production library uses AKS for key generation; they all use Miller-Rabin.
Conclusion
The Miller-Rabin primality test is the workhorse of modern cryptography, used every time an RSA key is generated or a prime is needed for Diffie-Hellman. This tool shows you exactly how it works, witness by witness, with the full modular exponentiation trace. For generating random primes rather than testing a specific number, use the Prime Number Generator. To compute Euler's totient of a number (which requires its prime factorization), see the Euler's Totient Calculator. To see where prime generation matters in practice, try the RSA Encrypt / Decrypt tool, which generates RSA keys whose security depends on the primality of p and q.