Projekt

Obecné

Profil

Stáhnout (2.43 KB) Statistiky
| Větev: | Revize:
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
};
    (1-1/1)