1 | var bn = require('bn.js');
|
2 | var brorand = require('brorand');
|
3 |
|
4 | function MillerRabin(rand) {
|
5 | this.rand = rand || new brorand.Rand();
|
6 | }
|
7 | module.exports = MillerRabin;
|
8 |
|
9 | MillerRabin.create = function create(rand) {
|
10 | return new MillerRabin(rand);
|
11 | };
|
12 |
|
13 | MillerRabin.prototype._randbelow = function _randbelow(n) {
|
14 | var len = n.bitLength();
|
15 | var min_bytes = Math.ceil(len / 8);
|
16 |
|
17 |
|
18 |
|
19 | do
|
20 | var a = new bn(this.rand.generate(min_bytes));
|
21 | while (a.cmp(n) >= 0);
|
22 |
|
23 | return a;
|
24 | };
|
25 |
|
26 | MillerRabin.prototype._randrange = function _randrange(start, stop) {
|
27 |
|
28 | var size = stop.sub(start);
|
29 | return start.add(this._randbelow(size));
|
30 | };
|
31 |
|
32 | MillerRabin.prototype.test = function test(n, k, cb) {
|
33 | var len = n.bitLength();
|
34 | var red = bn.mont(n);
|
35 | var rone = new bn(1).toRed(red);
|
36 |
|
37 | if (!k)
|
38 | k = Math.max(1, (len / 48) | 0);
|
39 |
|
40 |
|
41 | var n1 = n.subn(1);
|
42 | for (var s = 0; !n1.testn(s); s++) {}
|
43 | var d = n.shrn(s);
|
44 |
|
45 | var rn1 = n1.toRed(red);
|
46 |
|
47 | var prime = true;
|
48 | for (; k > 0; k--) {
|
49 | var a = this._randrange(new bn(2), n1);
|
50 | if (cb)
|
51 | cb(a);
|
52 |
|
53 | var x = a.toRed(red).redPow(d);
|
54 | if (x.cmp(rone) === 0 || x.cmp(rn1) === 0)
|
55 | continue;
|
56 |
|
57 | for (var i = 1; i < s; i++) {
|
58 | x = x.redSqr();
|
59 |
|
60 | if (x.cmp(rone) === 0)
|
61 | return false;
|
62 | if (x.cmp(rn1) === 0)
|
63 | break;
|
64 | }
|
65 |
|
66 | if (i === s)
|
67 | return false;
|
68 | }
|
69 |
|
70 | return prime;
|
71 | };
|
72 |
|
73 | MillerRabin.prototype.getDivisor = function getDivisor(n, k) {
|
74 | var len = n.bitLength();
|
75 | var red = bn.mont(n);
|
76 | var rone = new bn(1).toRed(red);
|
77 |
|
78 | if (!k)
|
79 | k = Math.max(1, (len / 48) | 0);
|
80 |
|
81 |
|
82 | var n1 = n.subn(1);
|
83 | for (var s = 0; !n1.testn(s); s++) {}
|
84 | var d = n.shrn(s);
|
85 |
|
86 | var rn1 = n1.toRed(red);
|
87 |
|
88 | for (; k > 0; k--) {
|
89 | var a = this._randrange(new bn(2), n1);
|
90 |
|
91 | var g = n.gcd(a);
|
92 | if (g.cmpn(1) !== 0)
|
93 | return g;
|
94 |
|
95 | var x = a.toRed(red).redPow(d);
|
96 | if (x.cmp(rone) === 0 || x.cmp(rn1) === 0)
|
97 | continue;
|
98 |
|
99 | for (var i = 1; i < s; i++) {
|
100 | x = x.redSqr();
|
101 |
|
102 | if (x.cmp(rone) === 0)
|
103 | return x.fromRed().subn(1).gcd(n);
|
104 | if (x.cmp(rn1) === 0)
|
105 | break;
|
106 | }
|
107 |
|
108 | if (i === s) {
|
109 | x = x.redSqr();
|
110 | return x.fromRed().subn(1).gcd(n);
|
111 | }
|
112 | }
|
113 |
|
114 | return false;
|
115 | };
|