Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download
80559 views
Tweet
Share
Share
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._rand = function _rand(n) {

14
  var len = n.bitLength();

15
  var buf = this.rand.generate(Math.ceil(len / 8));

16


17
  // Set low bits

18
  buf[0] |= 3;

19


20
  // Mask high bits

21
  var mask = len & 0x7;

22
  if (mask !== 0)

23
    buf[buf.length - 1] >>= 7 - mask;

24


25
  return new bn(buf);

26
}

27


28
MillerRabin.prototype.test = function test(n, k, cb) {

29
  var len = n.bitLength();

30
  var red = bn.mont(n);

31
  var rone = new bn(1).toRed(red);

32


33
  if (!k)

34
    k = Math.max(1, (len / 48) | 0);

35


36
  // Find d and s, (n - 1) = (2 ^ s) * d;

37
  var n1 = n.subn(1);

38
  var n2 = n1.subn(1);

39
  for (var s = 0; !n1.testn(s); s++) {}

40
  var d = n.shrn(s);

41


42
  var rn1 = n1.toRed(red);

43


44
  var prime = true;

45
  for (; k > 0; k--) {

46
    var a = this._rand(n2);

47
    if (cb)

48
      cb(a);

49


50
    var x = a.toRed(red).redPow(d);

51
    if (x.cmp(rone) === 0 || x.cmp(rn1) === 0)

52
      continue;

53


54
    for (var i = 1; i < s; i++) {

55
      x = x.redSqr();

56


57
      if (x.cmp(rone) === 0)

58
        return false;

59
      if (x.cmp(rn1) === 0)

60
        break;

61
    }

62


63
    if (i === s)

64
      return false;

65
  }

66


67
  return prime;

68
};

69


70
MillerRabin.prototype.getDivisor = function getDivisor(n, k) {

71
  var len = n.bitLength();

72
  var red = bn.mont(n);

73
  var rone = new bn(1).toRed(red);

74


75
  if (!k)

76
    k = Math.max(1, (len / 48) | 0);

77


78
  // Find d and s, (n - 1) = (2 ^ s) * d;

79
  var n1 = n.subn(1);

80
  var n2 = n1.subn(1);

81
  for (var s = 0; !n1.testn(s); s++) {}

82
  var d = n.shrn(s);

83


84
  var rn1 = n1.toRed(red);

85


86
  for (; k > 0; k--) {

87
    var a = this._rand(n2);

88


89
    var g = n.gcd(a);

90
    if (g.cmpn(1) !== 0)

91
      return g;

92


93
    var x = a.toRed(red).redPow(d);

94
    if (x.cmp(rone) === 0 || x.cmp(rn1) === 0)

95
      continue;

96


97
    for (var i = 1; i < s; i++) {

98
      x = x.redSqr();

99


100
      if (x.cmp(rone) === 0)

101
        return x.fromRed().subn(1).gcd(n);

102
      if (x.cmp(rn1) === 0)

103
        break;

104
    }

105


106
    if (i === s) {

107
      x = x.redSqr();

108
      return x.fromRed().subn(1).gcd(n);

109
    }

110
  }

111


112
  return false;

113
};

114


115