HesapHanem

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 about 3.18 × 1023. Depending on the server's maths 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 factorisation.
  • 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.

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 roughly 3.18 × 10²³ — far beyond what most applications ever need.

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.

Comments (1)

  • Editorial team

    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.

Popular calculators

Loan Calculator

Monthly payment, total interest and full amortization schedule.

Percentage Calculator

Percent change, percent of, and ratio calculations.

Discount Calculator

Calculate final price, savings, and discount amount.

BMI Calculator

Body mass index from height and weight (metric or imperial).

Age Calculator

Compute your exact age in years, months and days from a birth date.

Compound Interest Calculator

Calculate the final amount and interest earned with compounding.

All Calculators