Bug in the Miller-Rabin Test in BigInt.js 5.4

Doing Math with JavaScript

While experimenting with the Miller-Rabin primality test I have found a bug in the test implementation in the arbitrary-precision arithmetic library BigInt.js (in particular, the functions millerRabin and millerRabinInt). Leemon Baird, the author of BigInt.js, has been informed and will likely post a fix soon.

Affected versions: BigInt.js 5.4 and earlier versions.

Symptoms: For a few well-known strong pseudoprimes (SPSP), such as

SPSP to all bases 2 thru 7:      3215031751 = 151*751*28351
SPSP to all bases 2 thru 13:  3474749660383 = 1303*16927*157543
the output of millerRabin() and millerRabinInt() is incorrect. For example:
n=3215031751, base=11:     
millerRabinInt() returns 1 'probable prime' (expected 0 'composite')

n=3474749660383, base=17:  
millerRabinInt() returns 1 'probable prime' (expected 0 'composite')
(For information on the expected behavior of the test, see e.g. http://oeis.org/A014233 or
G. Jaeschke, On strong pseudoprimes to several bases, Mathematics of Computation, 61, 1993, 915-926.)

Test cases. Here is a bigger (but definitely not exhaustive) set of test cases for this bug:

Witness
base     Strong pseudoprime (liar base 2,3...)   Expected  Actual
 17      2152302898747 = 6763*10627*29947           0      1 (probable prime)
 17      3474749660383 = 1303*16927*157543          0      1 (probable prime)
 19      10710604680091 = 3739*18691*153259         0      1 (probable prime)
 17      130974307279201 = 991*2311*4951*11551      0      1 (probable prime)
 17      178147247320351 = 2311*11551*6673591       0      1 (probable prime)
 17      525529677519001 = 751*991*2311*305551      0      1 (probable prime)
 17      3797514195967801 = 991*2311*11551*143551   0      1 (probable prime)
 19      4498414682539051 = 46411*232051*417691     0      1 (probable prime)
 13      6830509209595831 = 21319*106591*3005839    0      1 (probable prime)
Bases 2, 3, 5, 7, 11 are liars; they are not expected to reveal compositeness in these cases. The witness bases 17, 19... listed in the left column do reveal compositeness in unaffected implementations. These same witness bases (or any other base tried!) do not reveal compositeness in BigInt 5.4.

In all of the above test cases, the bug no longer occurs after the following suggested fix in BigInt 5.4:

  //s=the highest power of two that divides mr_r
  /*
  k=0;
  for (i=0;i<mr_r.length;i++)
    for (j=1;j<mask;j<<=1)
      if (x[i] & j) {
        s=(k<mr_r.length+bpe ? k : 0);
         i=mr_r.length;
         j=mask;
      } else
        k++;
  */

  // FIX: replace the 9 lines commented above - with these 4 lines:
  if (isZero(mr_r)) return 0;
  for (k=0; mr_r[k]==0; k++);
  for (i=0,j=2; mr_r[k]%j==0; j*=2,i++ );
  s = k*bpe + i;

Copyright © 2012, Alexei Kourbatov, JavaScripter.net.