aboutsummaryrefslogtreecommitdiff
path: root/node_modules/miller-rabin
diff options
context:
space:
mode:
Diffstat (limited to 'node_modules/miller-rabin')
-rw-r--r--node_modules/miller-rabin/.npmignore2
-rw-r--r--node_modules/miller-rabin/1.js7
-rw-r--r--node_modules/miller-rabin/README.md26
-rwxr-xr-xnode_modules/miller-rabin/bin/miller-rabin29
-rw-r--r--node_modules/miller-rabin/lib/mr.js115
-rw-r--r--node_modules/miller-rabin/package.json32
-rw-r--r--node_modules/miller-rabin/test.js25
-rw-r--r--node_modules/miller-rabin/test/api-test.js18
8 files changed, 0 insertions, 254 deletions
diff --git a/node_modules/miller-rabin/.npmignore b/node_modules/miller-rabin/.npmignore
deleted file mode 100644
index 1ca957177..000000000
--- a/node_modules/miller-rabin/.npmignore
+++ /dev/null
@@ -1,2 +0,0 @@
-node_modules/
-npm-debug.log
diff --git a/node_modules/miller-rabin/1.js b/node_modules/miller-rabin/1.js
deleted file mode 100644
index 92953789e..000000000
--- a/node_modules/miller-rabin/1.js
+++ /dev/null
@@ -1,7 +0,0 @@
-'use strict';
-
-const BN = require('bn.js');
-
-const p = new BN('2e1b162f326430f5ac6af10f96b2a8350e01675d22324c9f', 'hex');
-
-console.log(p.bitLength());
diff --git a/node_modules/miller-rabin/README.md b/node_modules/miller-rabin/README.md
deleted file mode 100644
index e9d76f67c..000000000
--- a/node_modules/miller-rabin/README.md
+++ /dev/null
@@ -1,26 +0,0 @@
-# Miller-Rabin
-
-#### LICENSE
-
-This software is licensed under the MIT License.
-
-Copyright Fedor Indutny, 2014.
-
-Permission is hereby granted, free of charge, to any person obtaining a
-copy of this software and associated documentation files (the
-"Software"), to deal in the Software without restriction, including
-without limitation the rights to use, copy, modify, merge, publish,
-distribute, sublicense, and/or sell copies of the Software, and to permit
-persons to whom the Software is furnished to do so, subject to the
-following conditions:
-
-The above copyright notice and this permission notice shall be included
-in all copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
-OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
-MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
-NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
-DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
-OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
-USE OR OTHER DEALINGS IN THE SOFTWARE.
diff --git a/node_modules/miller-rabin/bin/miller-rabin b/node_modules/miller-rabin/bin/miller-rabin
deleted file mode 100755
index 2e18dfd53..000000000
--- a/node_modules/miller-rabin/bin/miller-rabin
+++ /dev/null
@@ -1,29 +0,0 @@
-#!/usr/bin/env node
-var bn = require('bn.js');
-var fs = require('fs');
-var mr = require('../').create();
-
-var num = '';
-if (process.argv[2]) {
- num += fs.readFileSync(process.argv[2]);
- start(num);
-} else {
- process.stdin.on('data', function(chunk) {
- num += chunk.toString().replace(/[^0-9a-f]/gi, '');
- });
- process.stdin.once('end', function() {
- start(num);
- });
-}
-
-function start(text) {
- var num = new bn(text, 16);
-
- var divisor = mr.getDivisor(num);
- if (!divisor)
- process.exit(1);
- if (divisor.cmpn(1) === 0)
- process.exit(0);
-
- console.log(divisor.toString(16));
-}
diff --git a/node_modules/miller-rabin/lib/mr.js b/node_modules/miller-rabin/lib/mr.js
deleted file mode 100644
index 60d2a8ef9..000000000
--- a/node_modules/miller-rabin/lib/mr.js
+++ /dev/null
@@ -1,115 +0,0 @@
-var bn = require('bn.js');
-var brorand = require('brorand');
-
-function MillerRabin(rand) {
- this.rand = rand || new brorand.Rand();
-}
-module.exports = MillerRabin;
-
-MillerRabin.create = function create(rand) {
- return new MillerRabin(rand);
-};
-
-MillerRabin.prototype._randbelow = function _randbelow(n) {
- var len = n.bitLength();
- var min_bytes = Math.ceil(len / 8);
-
- // Generage random bytes until a number less than n is found.
- // This ensures that 0..n-1 have an equal probability of being selected.
- do
- var a = new bn(this.rand.generate(min_bytes));
- while (a.cmp(n) >= 0);
-
- return a;
-};
-
-MillerRabin.prototype._randrange = function _randrange(start, stop) {
- // Generate a random number greater than or equal to start and less than stop.
- var size = stop.sub(start);
- return start.add(this._randbelow(size));
-};
-
-MillerRabin.prototype.test = function test(n, k, cb) {
- 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);
- 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 = this._randrange(new bn(2), n1);
- if (cb)
- cb(a);
-
- 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 false;
- if (x.cmp(rn1) === 0)
- break;
- }
-
- if (i === s)
- return false;
- }
-
- return prime;
-};
-
-MillerRabin.prototype.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);
- for (var s = 0; !n1.testn(s); s++) {}
- var d = n.shrn(s);
-
- var rn1 = n1.toRed(red);
-
- for (; k > 0; k--) {
- var a = this._randrange(new bn(2), n1);
-
- 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 false;
-};
diff --git a/node_modules/miller-rabin/package.json b/node_modules/miller-rabin/package.json
deleted file mode 100644
index af0f80573..000000000
--- a/node_modules/miller-rabin/package.json
+++ /dev/null
@@ -1,32 +0,0 @@
-{
- "name": "miller-rabin",
- "version": "4.0.1",
- "description": "Miller Rabin algorithm for primality test",
- "main": "lib/mr.js",
- "bin": "bin/miller-rabin",
- "scripts": {
- "test": "mocha --reporter=spec test/**/*-test.js"
- },
- "repository": {
- "type": "git",
- "url": "git@github.com:indutny/miller-rabin"
- },
- "keywords": [
- "prime",
- "miller-rabin",
- "bignumber"
- ],
- "author": "Fedor Indutny <fedor@indutny.com>",
- "license": "MIT",
- "bugs": {
- "url": "https://github.com/indutny/miller-rabin/issues"
- },
- "homepage": "https://github.com/indutny/miller-rabin",
- "devDependencies": {
- "mocha": "^2.0.1"
- },
- "dependencies": {
- "bn.js": "^4.0.0",
- "brorand": "^1.0.1"
- }
-}
diff --git a/node_modules/miller-rabin/test.js b/node_modules/miller-rabin/test.js
deleted file mode 100644
index 74b2ccfe4..000000000
--- a/node_modules/miller-rabin/test.js
+++ /dev/null
@@ -1,25 +0,0 @@
-var mr = require('./').create();
-var BN = require('bn.js');
-
-var p = new BN(
- `00:d3:99:af:83:02:de:91:f8:cc:1b:4e:2e:e0:18:
- b3:0a:41:a4:77:98:d2:ad:66:0f:dc:17:85:ca:58:
- b4:e4:88:55:c5:0a:82:08:7c:fb:70:a9:41:30:be:
- af:50:d2:ce:93:cd:46:83:47:6e:c0:51:a7:10:e6:
- 66:d1:08:e8:3d:b8:ce:fe:3e:4e:48:96:82:15:f7:
- 2c:83:80:05:f2:14:3a:a4:5a:44:2b:22:22:67:e5:
- 21:23:b7:cb:0f:71:5b:12:8b:3d:81:f6:5e:dc:99:
- 8f:f9:80:38:75:57:c2:dd:9b:7a:b2:24:97:42:60:
- 92:1f:1d:8a:68:c5:b8:7f:5d:c0:53:3d:15:f2:95:
- b8:1d:8b:c2:e6:ca:a6:4c:bd:bf:88:9f:3e:d3:d7:
- 24:18:27:62:6e:d0:52:75:68:9f:2a:c9:39:af:95:
- 55:bb:11:08:dc:51:e9:8b:5a:38:e0:c0:e9:d8:a6:
- 71:a5:03:f9:a7:2c:dd:1a:63:8e:7f:f0:36:68:a0:
- 44:f8:09:48:3d:bd:de:b3:2d:3a:2f:73:88:8a:0c:
- e2:7f:9b:dd:e8:c2:0e:ee:21:e4:a7:f9:4d:46:2f:
- a7:f6:6d:fa:88:2e:95:60:ac:53:2e:45:a2:9d:9e:
- c4:80:fc:c7:49:c9:42:bb:2b:66:f6:14:6d:7f:03:
- 4e:f3`.replace(/[^a-f0-9]/g, ''), 16);
-console.time();
-mr.test(p);
-console.timeEnd();
diff --git a/node_modules/miller-rabin/test/api-test.js b/node_modules/miller-rabin/test/api-test.js
deleted file mode 100644
index dee094d95..000000000
--- a/node_modules/miller-rabin/test/api-test.js
+++ /dev/null
@@ -1,18 +0,0 @@
-var assert = require('assert');
-var mr = require('../').create();
-var bn = require('bn.js');
-
-describe('Miller-Rabin', function() {
- it('should test number for primality', function() {
- assert(!mr.test(new bn(221)));
- assert(mr.test(new bn(257)));
-
- var p = new bn('dba8191813fe8f51eaae1de70213aafede8f323f95f32cff' +
- '8b64ebada275cfb18a446a0150e5fdaee246244c5f002ce0' +
- 'aca97584be1745f2dd1eea2849c52aac8c4b5fb78a1c4da7' +
- '052774338d3310a6e020c46168cb1f94014e9312511cc4fb' +
- '79d695bb732449f0e015745b86bfa371dc6ca7386e9c7309' +
- '5549c2e4b8002873', 16);
- assert(mr.test(p));
- });
-});