miller-rabin - npm Package Compare versions

Comparing version 1.0.1 to 1.0.2

lib/mr.js

 var bn = require('bn.js');
 var brorand = require('brorand');
 
-exports.test = function test(n, k) {
+function rand(n) {
   var len = n.bitLength();
+  var buf = brorand(Math.ceil(len / 8));
+
+  // Set low bits
+  buf[0] |= 3;
+
+  // Mask high bits
+  var mask = len & 0x7;
+  if (mask !== 0)
+    buf[buf.length - 1] >>= 7 - mask;
+
+  return new bn(buf);
+}
+
+exports.test = function test(n, k, cb) {
+  var len = n.bitLength();
   var red = bn.mont(n);
@@ -26,5 +41,5 @@ var rone = new bn(1).toRed(red);
   for (; k > 0; k--) {
-    do
-      var a = new bn(brorand(Math.ceil(len / 8)));
-    while (a.cmpn(2) < 0 || a.cmp(n2) > 0);
+    var a = rand(n2);
+    if (cb)
+      cb(a);
 
@@ -50,1 +65,47 @@ var x = a.toRed(red).redPow(d);
 };
+
+exports.getDivisor = function getDivisor(n, k) {
+  var len = n.bitLength();
+  var red = bn.mont(n);
+  var rone = new bn(1).toRed(red);
+
+  if (!k)
+    k = Math.max(1, (len / 48) | 0);
+
+  // Find d and s, (n - 1) = (2 ^ s) * d;
+  var n1 = n.subn(1);
+  var n2 = n1.subn(1);
+  for (var s = 0; !n1.testn(s); s++) {}
+  var d = n.shrn(s);
+
+  var rn1 = n1.toRed(red);
+
+  var prime = true;
+  for (; k > 0; k--) {
+    var a = rand(n2);
+
+    var g = n.gcd(a);
+    if (g.cmpn(1) !== 0)
+      return g;
+
+    var x = a.toRed(red).redPow(d);
+    if (x.cmp(rone) === 0 || x.cmp(rn1) === 0)
+      continue;
+
+    for (var i = 1; i < s; i++) {
+      x = x.redSqr();
+
+      if (x.cmp(rone) === 0)
+        return x.fromRed().subn(1).gcd(n);
+      if (x.cmp(rn1) === 0)
+        break;
+    }
+
+    if (i === s) {
+      x = x.redSqr();
+      return x.fromRed().subn(1).gcd(n);
+    }
+  }
+
+  return prime;
+};

package.json

 {
   "name": "miller-rabin",
-  "version": "1.0.1",
+  "version": "1.0.2",
   "description": "Miller Rabin algorithm for primality test",
@@ -5,0 +5,0 @@ "main": "lib/mr.js",

No alert changes

Improved metrics

Total package byte prevSize

4684

29.97%

Lines of code

100

85.19%

No dependency changes