Miller-Rabin Primality Test Calculator

Miller-Rabin primality test: multi-round probabilistic with (1/4)^k error, deterministic for n<3.3e24, Fermat comparison and Carmichael numbers handling.

Calculation parameters
Scegli la variante del test.
Numero intero da testare (2 <= n <= 1e15 per calcolo JS esatto).
Base a per il testimone singolo. 2 e' la piu' usata.
Numero di testimoni casuali. Probabilita' di errore <= (1/4)^k.
Was this calculator useful?

The Miller-Rabin test

The Miller-Rabin primality test is the world's most-used algorithm for deciding whether a natural number is prime. Developed by Gary Miller (1976) as a deterministic algorithm conditional on the generalised Riemann hypothesis, modified by Michael O. Rabin (1980) into an unconditional probabilistic form, it underlies every key generation in RSA, DSA, Diffie-Hellman and the primality tests in OpenSSL, GnuPG, Mathematica, Python (sympy.isprime), Java (BigInteger.isProbablePrime).

The algorithm

For odd n > 3, write n − 1 = d · 2^s with d odd. To test with base a:

  1. Compute x0 = ad mod n.
  2. If x0 = 1 or x0 = n − 1, n is probably prime.
  3. Otherwise compute xi+1 = xi2 mod n for i = 0, ..., s − 2. If any xi = n − 1, probably prime.
  4. Otherwise n is definitely composite and a is a witness.

The test relies on the fact that in ℤ/pℤ with p prime, the only non-trivial square roots of 1 are ±1. Finding b with b² ≡ 1 (mod n) but b ≠ ±1 proves n composite.

The four modes

  1. Single test: Miller-Rabin with a specific base a, showing all intermediate steps.
  2. Multi-round random: k random-base rounds. False-positive probability <= (1/4)^k. For k = 20: < 10^-12.
  3. Deterministic: uses fixed bases {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} for deterministic result on n < 3.317·10^24 (Sorenson-Webster 2015). Faster than AKS.
  4. Fermat comparison: shows how Miller-Rabin distinguishes Carmichael numbers from true primes.

Error probability

Rabin (1980) proved: for any composite n, at least 3/4 of bases in [2, n − 2] are witnesses. So a single round with a random base has error probability <= 1/4. k independent rounds give error 99% of bases are witnesses.

Deterministic variant

With enough fixed bases, Miller-Rabin becomes deterministic for bounded n:

  • n < 2,047: test a = 2.
  • n < 1,373,653: {2, 3}.
  • n < 9,080,191: {31, 73}.
  • n < 4,759,123,141: {2, 7, 61}.
  • n < 3.317·10^24: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} (Sorenson-Webster 2015).

For larger n, Miller-Rabin remains probabilistic but with practically null error at k = 20-40 rounds. For absolute certainty there is AKS (Agrawal-Kayal-Saxena 2002, O((log n)^(6+ε))), but it is much slower in practice.

Carmichael numbers

Carmichael numbers (discovered 1910) are composites that pass the Fermat test for every coprime base. First few:

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, ...

1729 is the Hardy-Ramanujan number; 561 = 3·11·17 is the smallest. Alford-Granville-Pomerance (1994) proved there are infinitely many, but they are rare: only 2,163 below 10^9. Miller-Rabin detects them correctly via the non-trivial-root-of-1 check.

Practical applications

  • RSA key generation: large primes (1024-2048 bits) tested with k = 40 rounds. Error < 10^-24.
  • TLS handshake: Diffie-Hellman parameters and elliptic curves need verified primes.
  • Blockchain: Bitcoin, Ethereum use Miller-Rabin on elliptic-curve primes (secp256k1).
  • OpenSSL: BN_is_prime_ex() combines trial division + Miller-Rabin.
  • Python: sympy.isprime() and gmpy2.is_prime() implement Miller-Rabin with BPSW enhancements.
  • Digital certificates: CAs verify primality in RSA signatures of X.509 certs.

Comparison with other tests

  • Trial division: exact but O(√n), too slow for n > 10^12.
  • Fermat: O(log n) per round but fooled by Carmichael.
  • Solovay-Strassen (1977): similar but worse error (1/2 per round).
  • Baillie-PSW (BPSW): Miller-Rabin base 2 + Lucas test. No known counterexample up to 2^64.
  • AKS (2002): first deterministic polynomial-time test. O((log n)^(6+ε)).
  • ECPP: produces verifiable primality certificate. O((log n)^4), used for world records.

Updated July 2026

Frequently Asked Questions

What is the Miller-Rabin test?

It is the most used primality algorithm in the world for deciding whether a number is prime. Developed by Miller in 1976 (deterministic under the generalized Riemann hypothesis) and made unconditionally probabilistic by Rabin in 1980, it is very fast and highly reliable, at the base of RSA, TLS and cryptocurrencies.

How does the algorithm work?

For odd n you write n-1 = d x 2^s with d odd. Choosing a base a, you compute x = a^d mod n: if x = 1 or x = n-1, n is probably prime. Otherwise you repeatedly square; if some value becomes n-1, n is probably prime, otherwise it is composite with witness a.

What modes does the calculator offer?

Four: a single round with a chosen base, multi-round with k random witnesses and error estimate, a deterministic test with fixed bases, and a direct comparison between Fermat and Miller-Rabin. Each mode flags Carmichael numbers and shows the steps of the algorithm.

How reliable is a probabilistic test?

Each round has an error probability of at most 1/4 for a composite, and the rounds are independent: with k witnesses the error drops to (1/4)^k. With 40 rounds (as in RSA) the error is below 10^-24, far lower than the probability that a cosmic ray corrupts the memory during the computation.

What is a Carmichael number?

It is a composite number that fools the Fermat test: it satisfies a^(n-1) congruent to 1 mod n for every base coprime with n, despite not being prime. The first are 561, 1105, 1729, 2465. Miller-Rabin is not fooled thanks to the check of non-trivial square roots of 1.

What is the difference from the Fermat test?

The Fermat test only checks a^(n-1) congruent to 1 mod n and fails on Carmichael numbers. Miller-Rabin adds the check that, when squaring, a non-trivial square root of 1 (different from +1 and -1) does not appear. This stronger condition makes Miller-Rabin robust where Fermat errs.

Can the test be deterministic?

Yes. For numbers below a known threshold, testing a fixed set of bases guarantees a certain result: the bases {2,3,5,7,11,13,17,19,23,29,31,37} are deterministic for n < 3.3 x 10^24 (Sorenson-Webster 2015). For n up to 10^12, {2,3,5,7,11} suffice, for n up to 10^9, {2,7,61} suffice.

Where is Miller-Rabin used?

In RSA key generation (with about 40 rounds), in TLS and Diffie-Hellman key exchange, in elliptic curves such as Bitcoin's secp256k1, and in libraries such as OpenSSL, sympy and gmpy2. It is the standard method because it combines speed and practically absolute reliability.

Comments (0)

No comments yet. Be the first!