diff options
Diffstat (limited to 'node_modules/miller-rabin')
-rw-r--r-- | node_modules/miller-rabin/.npmignore | 2 | ||||
-rw-r--r-- | node_modules/miller-rabin/1.js | 7 | ||||
-rw-r--r-- | node_modules/miller-rabin/README.md | 26 | ||||
-rwxr-xr-x | node_modules/miller-rabin/bin/miller-rabin | 29 | ||||
-rw-r--r-- | node_modules/miller-rabin/lib/mr.js | 115 | ||||
-rw-r--r-- | node_modules/miller-rabin/package.json | 32 | ||||
-rw-r--r-- | node_modules/miller-rabin/test.js | 25 | ||||
-rw-r--r-- | node_modules/miller-rabin/test/api-test.js | 18 |
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)); - }); -}); |