Miller-Rabin Primality Test Calculator

Enter a non-negative integer to test it for primality with Miller-Rabin.

How it is calculated

Enter a whole number n (digits only; negatives, decimals and commas are refused). Values below 2 are reported as composite. The tool first divides by the primes 2 to 37; a match decides it at once (n equal to that prime is prime, otherwise composite, and that prime is shown as the witness). Otherwise it writes n − 1 = 2s · d with d odd and tests each base a in 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. A base passes if ad ≡ ±1 (mod n) or a2r·d ≡ −1 (mod n) for some r below s. The first base that fails proves n composite and is shown as the witness. If all pass, n is prime; with these twelve bases that is certain below 318,665,857,834,031,151,167,461 (about 3.18 × 1023, the smallest strong pseudoprime to all twelve, per Sorenson and Webster). From that size on the verdict reads “probably prime” instead. Depending on the server's math library, numbers above 263 − 1 can come back as Unknown rather than a verdict. The words prime and composite appear in English.

Worked example

Test n = 3215031751. It has no prime factor up to 37, so the trial division finds nothing. Then n − 1 = 3215031750 = 21 × 1607515875, so s = 1 and d = 1607515875. Bases 2, 3, 5 and 7 all pass, so a test using only those four would call n prime. Base 11 gives a result that is neither 1 nor n − 1, so it fails. The tool reports composite with witness 11. By contrast, 97 gives prime, and its witness shows a dash.

Try this example →

Common mistakes

  • Reading the witness as a factor of n. For 1681 (41 × 41) the witness is 2, a base that failed the test, while for 561 it is 3, which really does divide 561. Neither is a full factorization.
  • Expecting a prime to show a witness. A dash means no base found a problem, which is the result for primes.
  • Running only base 2 by hand and trusting it. Some composites, such as 2047 = 23 × 89, pass base 2 alone; several bases are needed, which is why the tool tries twelve.
  • Entering 1, 0 or a negative number and expecting a primality verdict. 1 and 0 are shown as composite, though neither is a composite number in the strict sense, and negatives return nothing.
  • Pasting a number with commas, spaces inside it, a decimal point or a sign. Only plain digits are accepted.

Sources

About this calculator

The Miller-Rabin test checks primality by writing n − 1 as 2ˢ·d with d odd, then testing whether a witness base a satisfies aᵈ ≡ 1 (mod n) or a^(2ʳ·d) ≡ −1 (mod n) for some r < s. A single witness only gives a probabilistic result, but testing against a small, proven set of fixed witness bases (for example 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) makes the test deterministic for every integer below 318,665,857,834,031,151,167,461 (about 3.18 × 10²³, Sorenson and Webster 2015) — far beyond what most applications ever need. From that size on, a number that passes all twelve bases is reported as probably prime, because a strong pseudoprime to those bases exists at that bound; a composite verdict is always certain.

Cryptographers and software developers use exactly this kind of test when generating large prime candidates for RSA or Diffie-Hellman keys, and computer science students use it to see, on real numbers, why Miller-Rabin scales so much better than trial division for checking whether a big integer is prime.

Was this helpful?

You can pick up to 3 reactions.

Note from the editors

Read the witness column with care. When a small prime divides the number, the witness is that prime itself, so 561 reports 3 and you can divide it out to start factoring. When a base catches the number, the witness only proves it is composite and is not a factor. Entering a number that is prime shows a dash. Are you checking numbers for a crypto exercise, a puzzle or class work? Tell us which sizes you try.

Comments

  • Be the first to comment.

Popular calculators

All Calculators