Miller-Rabin Primality Test

A Fast Primality Test in JavaScript:
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). For each round, choose (randomly or at will) a new integer 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 to base(s) a, and such bases 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 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 n. 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 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⁵³)

leastFactor_('n') (same as above, except n is expected to be a string with up to 20 digits)

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 string (of any length) that holds the digits of n. If, instead of a string, you pass an odd number n less than 2⁵³ to these functions, the test will still work. However, if you try to pass an odd number n greater than 2⁵³, 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: JavaScript/IEEE754 cannot exactly represent odd numbers that large!

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 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 (strong pseudoprimes) for each base less than or equal to the kth prime a = 2,3,5,7... This means that, for these liar bases a, the test miller_rabin(n,a) returns 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*798330580441

The 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 Online Encyclopedia of Integer Sequences, 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... would produce exactly the same results as a = 2,3,4..., thus yielding no additional information at all. Examples:

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 and a = n-1 are never used – for a reason: these bases would result in odd composite 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 and any multiples of n are never used – also for a reason: these bases would result in a prime 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⁵³. Intermediate calculations in the Miller-Rabin test may involve numbers greater than that, even if the number n itself is under 2⁵³. 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().

A Fast Primality Test in JavaScript: the Miller-Rabin Primality Test

A Fast Primality Test in JavaScript:
the Miller-Rabin Primality Test