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",

New alerts