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

Doing Math with JavaScript

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 < 253`)
• `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 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: JavaScript/IEEE754 cannot exactly represent odd numbers that large!

Average: %
Average: %
Average: %
Average: %
Average: %
Average: %
Average: %
Average: %
Average: %
Average: %

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 253. Intermediate calculations in the Miller-Rabin test may involve numbers greater than that, even if the number `n` itself is under 253. 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()`.