The Miller-Rabin primality test is among the fastest and most widely used primality tests in computational practice.
The algorithm of the test is as follows:
Given a large odd integer
n to be tested,
compute one or more rounds of the test (see the pseudocode);
we will refer to each round as
a called the base;
it must be at least
2 and at most
Each round's result can be either
0 (composite) or
1 (probable prime).
If any round returns
0 (composite), then
n is certain to be composite; no further rounds are needed.
If all rounds return
1 (probable prime), then
n is highly likely to be prime.
In rare cases, our probable prime
n might in fact be composite;
n is called a strong pseudoprime
a are called strong liars for
Comparing the speed of the Miller-Rabin test to a trial division test.
n, a brute force trial division test is much faster.
For very large prime
n, the Miller-Rabin test is the winner; for example, in Google Chrome 11 on a modern 2.5GHz laptop
(a) 30 rounds of the Miller-Rabin test for a 19-digit prime take about 30 milliseconds, and
(b) 30 rounds for a 30-digit prime take about 45 milliseconds; so a single round takes about 1.0ms to 1.5ms.
The trial division test becomes extremely slow as
n grows larger
(it takes 1 minute for a 19-digit prime in the same browser on the same machine);
trial division is of very little use for large prime
This is because the execution time of the Miller-Rabin test grows only modestly, as a polynomial function of the input size,
while the execution time of a trial division test for prime
n grows very significantly, exponentially with the input size.
(This follows from the fact that, for prime
n, the number of operations in a trial division test is proportional to the square root of
The input size in primality tests is the number of digits of
leastFactor(n)(a trial-division search for the least prime factor of the number
n < 253)
leastFactor_('n')(same as above, except
nis expected to be a string with up to 20 digits)
miller_rabin('n','a')(a single round of the Miller-Rabin test, base
isPrimeMR3('n')(3 rounds of the Miller-Rabin test for bases
isPrimeMR6('n')(6 rounds of the Miller-Rabin test for prime bases up to
isPrimeMR10('n')(10 rounds of the Miller-Rabin test for prime bases up to
isPrimeMR30('n')(30 rounds of the Miller-Rabin test for prime bases up to
Caution! In the above test functions, the argument
'n' is a string (of any length) that holds the digits of
If, instead of a string, you pass an odd number
less than 253 to these functions, the test will still work.
However, if you try to pass an odd number
n greater than 253,
without apostrophes, the test will not work because the argument would actually turn out to be some other number
approximately equal to the desired odd number:
The Miller-Rabin test is a probabilistic primality test because, in general, the
probable prime result at any round does not guarantee primality and, moreover, the test outcome
depends not only on
n being prime but also on our choice of the bases
The more rounds with different bases
a we perform, the higher the reliability of the test.
For smaller numbers
n, a couple of rounds may be good enough; e.g. just two rounds with bases 2 and 3
are proven to correctly determine the primality of any odd
n from 5 to 1373651.
For very large
n, even ten rounds might still be insufficient, depending on our desired level of confidence.
For example, the following composite numbers
n are known false-positives in the Miller-Rabin test (strong pseudoprimes)
for each base less than or equal to the kth prime
a = 2,3,5,7...
1 (probable prime) even though the number
n is in fact composite.
Strong pseudoprime (SPSP) to base 2: 2047 = 23*89 SPSP to both base 2 and base 3: 1373653 = 829*1657 SPSP to all bases 2 thru 5: 25326001 = 2251*11251 SPSP to all bases 2 thru 7: 3215031751 = 151*751*28351 SPSP to all bases 2 thru 11: 2152302898747 = 6763*10627*29947 SPSP to all bases 2 thru 13: 3474749660383 = 1303*16927*157543 SPSP to all bases 2 thru 19: 341550071728321 = 10670053*32010157 SPSP to all bases 2 thru 31: 3825123056546413051 = 149491*747451*34233211 SPSP to all bases 2 thru 37: 318665857834031151167461 = 399165290221*798330580441The numbers
n = 3825123056546413051and
n = 318665857834031151167461(the last two lines) have thirty or more liar bases
a<40, including more than ten prime liar bases. This example shows that, indeed, ten rounds may not be enough if
nis this big. Fortunately, additional rounds with more bases always allow the test to discover that a pseudoprime
nis composite. For more information on pseudoprimes, see sequences A014233 and A074773 from the Online Encyclopedia of Integer Sequences,
oeis.org; see also further references there.
(1) Computations of the Miller-Rabin test are in modular arithmetic (
Therefore, bases greater than
n, such as
a = n+2,n+3,n+4...
a = 2,3,4...
miller_rabin(2047,11) // 1 (probable prime) miller_rabin(2047,2058) // 1 (probable prime) 2058 = 2047 + 11 miller_rabin(2047,3) // 0 (composite) miller_rabin(2047,2050) // 0 (composite) 2050 = 2047 + 3
a = 1
a = n-1
n reported as probable prime,
i.e. these bases are strong liars for odd composite
n. Examples of incorrect base choice:
miller_rabin(25,1) // 1 (probable prime) - even though 25 is composite miller_rabin(25,24) // 1 (probable prime) - even though 25 is composite miller_rabin(91,1) // 1 (probable prime) - even though 91 is composite miller_rabin(91,90) // 1 (probable prime) - even though 91 is composite
a = n
n misreported as composite.
That's something that never happens in the Miller-Rabin test under normal conditions.
(Once again, the normal conditions are that
n should be a big odd integer;
a should be at least
2 and at most
Examples of incorrect base choice of this kind:
miller_rabin(29,29) // 0 (composite) - even though 29 is prime miller_rabin(29,58) // 0 (composite) - even though 29 is prime miller_rabin(7,7) // 0 (composite) - even though 7 is prime miller_rabin(7,21 ) // 0 (composite) - even though 7 is prime
Intermediate calculations in the Miller-Rabin test may involve numbers greater than that,
even if the number
n itself is under 253.
library in order to handle large numbers. The test implementation on this page uses
an arbitrary precision arithmetic library that has been developed and placed in the public domain by Professor Leemon Baird.
Many thanks Prof. Baird!
(5) BigInt.js 5.4 and earlier versions have a
bug in the Miller-Rabin test implementation.
Tests on this page are not affected because our function
was written to call lower-level operations of BigInt.js
it does not call the affected BigInt.js functions