the Miller-Rabin Primality Test

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 `miller_rabin(n,a)`

.`a`

called the *base*;
it must be *at least* `2`

and *at most* `n-2`

.
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;
if so, `n`

is called a *strong pseudoprime* `a`

,`a`

are called *strong liars* for `n`

.

**Comparing the speed of the Miller-Rabin test to a trial division test.**
For small `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

`n`

grows larger
(it takes 1 minute for a `n`

.
This is because the execution time of the Miller-Rabin test grows only modestly, as a `n`

grows very significantly, `n`

, the number of operations in a trial division test is proportional to the square root of `n`

.
The input size in primality tests is the number of digits of `n`

.)
Below you can run the tests yourself and compare the execution times of these JavaScript functions:
`leastFactor(n)`

(a trial-division search for the least prime factor of the number `n < 2`^{53}

)`leastFactor_('n')`

(same as above, except `n`

is expected to be a `miller_rabin('n','a')`

(a single round of the Miller-Rabin test, base `a`

)
`isPrimeMR3('n')`

(3 rounds of the Miller-Rabin test for bases `2,3,5`

)
`isPrimeMR6('n')`

(6 rounds of the Miller-Rabin test for prime bases up to `13`

)
`isPrimeMR10('n')`

(10 rounds of the Miller-Rabin test for prime bases up to `29`

)
`isPrimeMR30('n')`

(30 rounds of the Miller-Rabin test for prime bases up to `113`

)
** Caution!** In the above test functions, the argument

`'n'`

is a `n`

.
If, instead of a string, you pass an odd `n`

less than 2`n`

**The Miller-Rabin test is a probabilistic primality test** because, in general, the

`n`

being prime but also on our choice of the bases `a`

.
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 (`a = 2,3,5,7...`

`a`

,
the test `miller_rabin(n,a)`

returns `1`

(`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 = 3825123056546413051`

and `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 `n`

is this big.
Fortunately, additional rounds with more bases always allow the test to discover that
a pseudoprime `n`

is composite.
For more information on pseudoprimes, see sequences
A014233 and
A074773 from the
`oeis.org`

;
see also further references there.
**Notes:**

(1) Computations of the Miller-Rabin test are in modular arithmetic (`mod n`

).
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

(2) Bases `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

(3) Bases `a = n`

`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;
the base `a`

should be *at least* `2`

and *at most* `n-2`

.)
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

(4) JavaScript variables cannot natively represent odd numbers over 2^{53}.
Intermediate calculations in the Miller-Rabin test may involve numbers greater than that,
even if the number `n`

itself is under 2^{53}.
Therefore, a JavaScript implementation of the Miller-Rabin test must rely on some *big integer arithmetic*
library in order to handle large numbers. The test implementation on this page uses
`BigInt.js`

,
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 `miller_rabin()`

was written to call lower-level operations of BigInt.js –
it does ** not** call the affected BigInt.js functions

`millerRabin()`

and `millerRabinInt()`

.

Copyright © 1999-2011, JavaScripter.net.