Miller Rabin Primality Test Error on JavaScript

Question

Im working on JavaScript to get three different algorithms to work in the same code, I set up a function for each algorithm. I'm trying to get three Primality testing methods: Trial Division, the Fermat Primality Test, and the Miller-Rabin Primality Test. The first two are working fine but the Miller-Rabin isn't. I'm pretty new to JavaScript and programming in general, so if you can find where I went wrong or can think of a way to make it work, please let me know! Thanks!

// 1531 6389 68819 688889 6388819
// 68883889 688838831 1000000009
// 561 is a Carmichael number; a Fermat pseudoprime with the property a^n-1 = 1 mod n, for any "a" coprime to 561.
input = 5491763;
numTrials = 2000;

document.getElementById("input").innerHTML = input;

function TrialDiv(n) {

  if (n === 1) {
    return false;
  } else if (n === 2) {
    return true;
  } else {
    for (var x = 2; x < n; x++) {
      if (n % x === 0) {
        return false;
      }
    }
    return true;
  }
}

if ((TrialDiv(input)) === true) {
  a = "Prime"
} else if ((TrialDiv(input)) === false) {
  a = "Composite"
}
//---------------------------------------------------------------------------
function gcd(x, y) {
  while (y !== 0) {
    var z = x % y;
    x = y;
    y = z;
  }
  return x;
}

function getRndInteger(max) {
  return Math.floor(Math.random() * (max - 2)) + 2;
}
//--------------------------------------------------------------------------
function Fermat(n) {

  for (var t = 0; t = numTrials; t++) {
    m = getRndInteger(input);
    if (gcd(m, n) !== 1) {
      return false;
    }
  }
  return (Math.pow(m, n - 1) % n !== 1);
}

if ((Fermat(input)) === true) {
  b = "Prime";
} else if ((Fermat(input)) === false) {
  b = "Composite";
}
//---------------------------------------------------------------------------
function genD(n) { // Generates "d" such that "n-1 = 2^s * d"
  var p = n - 1;
  var d = p / 2;
  while (d % 2 === 0) {
    d = d / 2;
  }
  return d;
}

function genS() { // Generates "s" such that "n-1 = 2^s * d"
  var s = Math.log2(p / d);
  return s;
}
//---------------------------------------------------------------------------
function MillerRabin(n) {

  for (var t = 0; t < numTrials; t++) {
    m = getRndInteger(input);
    if (gcd(m, n) !== 1) {
      return false;
    } else {
      for (var r = 0; r < genS(); r++) {
        power = (Math.pow(2, r) * genD(input));
        if (Math.pow(m, genD(input)) % n === 1 || Math.pow(m, power) % n === -1) {
          return true;
        } else {
          return false;
        }
      }
      return true;
    }
    return true;
  }
}

if ((MillerRabin(input)) === true) {
  c = "Prime";
} else if ((MillerRabin(input)) === false) {
  c = "Composite";
}

<body>
  <button type="button" onclick='document.getElementById("TrialDivision").innerHTML = a;  document.getElementById("FermatTest").innerHTML = b; document.getElementById("MillerRabinTest").innerHTML = c; '>Show</button>

  <hr>
  <b style="color:rgb(0,0,120)">PRIMALITY TESTS</b>
  <p></p>
  Input:
  <l id="input"></l>

  <hr>
  <h5 style="color:rgb(160,0,0)">TRIAL DIVISION</h5>
  <p></p>
  Output:
  <i id="TrialDivision"></i>

  <hr>
  <h5 style="color:rgb(160,0,0)">FERMAT PRIMALITY TEST</h5>
  <p></p>
  Output:
  <i id="FermatTest"></i>

  <hr>
  <h5 style="color:rgb(160,0,0)">MILLER-RABIN PRIMALITY TEST</h5>
  <p></p>
  Output:
  <i id="MillerRabinTest"></i>
</body>
<script>

That's how I wrote it up, this was purely created by me from the original mathematical algorithms for each test. What happens is that the Miller-Rabin Output doesn't show anything when the input number is prime; the algorithm isn't able to identify it. But it does identify composites correctly.

Please let me know of any improvements you think of!

What debugging have you done? Where do the errors come from? — Carcigenicate
What happens is the Miller-Rabin "Output" shows nothing when the input number is prime, but correctly identifies composites. — Agus Perez Del Castillo
You should fix your indentation. You're probably missing a return statement in a branch somewhere. It's difficult to tell though when things are indented improperly. — Carcigenicate
Thanks for the tip, I just edited it and did the tidying up to show indentation better. I thought of the missing a return issue before and checked, but I couldn't think of where it could be missing. — Agus Perez Del Castillo
When you say that it doesn't show anything, what specifically is the output of the MillerRabin function? — Carcigenicate

Mark Mark · Accepted Answer · 2017-07-30T02:07:06

You have some problems with loops not running. I'm not sure how the algorithm is supposed to work, so I don't if it's working or not, but the immediate problem is cause by leaky variable and variables not declared in functions (which makes them global).

The fix for this immediate problem is to declare the local variables in the functions so you don't depend on having them set by some other function.

function genD(n) { // Generates "d" such that "n-1 = 2^s * d"
    var p = n - 1;
    var d = p / 2;
    while (d % 2 === 0) {
        d = d / 2;
    }
    return d;
}

function genS(n) { // Generates "s" such that "n-1 = 2^s * d"
    var p = n - 1
    var d = p / 2
    var s = Math.log2(p / d);
    return s;
}

Once you start fixing the errors that crash there are a few other big problems. For example your fermat() potentially runs for ever:

for (var t = 0; t = numTrials; t++) {

Should be:

for (var t = 0; t == numTrials; t++) {

= sets t to numTrails for every loop

I think you should start at the beginning, put all your functions together and all you other logic code that calls the functions together so you can see what's going on.

Miller Rabin Primality Test Error on JavaScript

1 Answers