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
|
// Generage random bytes until a number less than n is found.
|
18
|
// This ensures that 0..n-1 have an equal probability of being selected.
|
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
|
// Generate a random number greater than or equal to start and less than stop.
|
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
|
// Find d and s, (n - 1) = (2 ^ s) * d;
|
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
|
// Find d and s, (n - 1) = (2 ^ s) * d;
|
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
|
};
|