Projekt

Obecné

Profil

Stáhnout (2.18 KB) Statistiky
| Větev: | Revize:
1
var randomBytes = require('randombytes');
2
module.exports = findPrime;
3
findPrime.simpleSieve = simpleSieve;
4
findPrime.fermatTest = fermatTest;
5
var BN = require('bn.js');
6
var TWENTYFOUR = new BN(24);
7
var MillerRabin = require('miller-rabin');
8
var millerRabin = new MillerRabin();
9
var ONE = new BN(1);
10
var TWO = new BN(2);
11
var FIVE = new BN(5);
12
var SIXTEEN = new BN(16);
13
var EIGHT = new BN(8);
14
var TEN = new BN(10);
15
var THREE = new BN(3);
16
var SEVEN = new BN(7);
17
var ELEVEN = new BN(11);
18
var FOUR = new BN(4);
19
var TWELVE = new BN(12);
20
var primes = null;
21

    
22
function _getPrimes() {
23
  if (primes !== null)
24
    return primes;
25

    
26
  var limit = 0x100000;
27
  var res = [];
28
  res[0] = 2;
29
  for (var i = 1, k = 3; k < limit; k += 2) {
30
    var sqrt = Math.ceil(Math.sqrt(k));
31
    for (var j = 0; j < i && res[j] <= sqrt; j++)
32
      if (k % res[j] === 0)
33
        break;
34

    
35
    if (i !== j && res[j] <= sqrt)
36
      continue;
37

    
38
    res[i++] = k;
39
  }
40
  primes = res;
41
  return res;
42
}
43

    
44
function simpleSieve(p) {
45
  var primes = _getPrimes();
46

    
47
  for (var i = 0; i < primes.length; i++)
48
    if (p.modn(primes[i]) === 0) {
49
      if (p.cmpn(primes[i]) === 0) {
50
        return true;
51
      } else {
52
        return false;
53
      }
54
    }
55

    
56
  return true;
57
}
58

    
59
function fermatTest(p) {
60
  var red = BN.mont(p);
61
  return TWO.toRed(red).redPow(p.subn(1)).fromRed().cmpn(1) === 0;
62
}
63

    
64
function findPrime(bits, gen) {
65
  if (bits < 16) {
66
    // this is what openssl does
67
    if (gen === 2 || gen === 5) {
68
      return new BN([0x8c, 0x7b]);
69
    } else {
70
      return new BN([0x8c, 0x27]);
71
    }
72
  }
73
  gen = new BN(gen);
74

    
75
  var num, n2;
76

    
77
  while (true) {
78
    num = new BN(randomBytes(Math.ceil(bits / 8)));
79
    while (num.bitLength() > bits) {
80
      num.ishrn(1);
81
    }
82
    if (num.isEven()) {
83
      num.iadd(ONE);
84
    }
85
    if (!num.testn(1)) {
86
      num.iadd(TWO);
87
    }
88
    if (!gen.cmp(TWO)) {
89
      while (num.mod(TWENTYFOUR).cmp(ELEVEN)) {
90
        num.iadd(FOUR);
91
      }
92
    } else if (!gen.cmp(FIVE)) {
93
      while (num.mod(TEN).cmp(THREE)) {
94
        num.iadd(FOUR);
95
      }
96
    }
97
    n2 = num.shrn(1);
98
    if (simpleSieve(n2) && simpleSieve(num) &&
99
      fermatTest(n2) && fermatTest(num) &&
100
      millerRabin.test(n2) && millerRabin.test(num)) {
101
      return num;
102
    }
103
  }
104

    
105
}
(2-2/3)