高速指数演算と素数判定

// Generated by CoffeeScript 2.5.1
(function() {
  // 指数
  var gen_prime, gen_rand, modular_exp, mr_primary_test;

  modular_exp = function(a, b, n) {
    var res;
    res = 1n;
    while (b !== 0n) {
      if ((b & 1n) !== 0n) {
        res = (res * a) % n;
      }
      a = (a ** 2n) % n;
      b = b >> 1n;
    }
    return res;
  };

  // ランダムな素数
  gen_rand = function(bit_length) {
    var bits, ref, ret;
    bits = (function() {
      var results = [];
      for (var i = 0, ref = bit_length - 2; 0 <= ref ? i < ref : i > ref; 0 <= ref ? i++ : i--){ results.push(i); }
      return results;
    }).apply(this).map(function() {
      return Math.floor(Math.random() * 2);
    });
    ret = 1n;
    bits.forEach(function(b) {
      return ret = ret * 2n + BigInt(b);
    });
    return ret * 2n + 1n;
  };

  // 素数判定
  mr_primary_test = function(n, k = 100) {
    var d, nb, r, res, s;
    if (n === 1n) {
      return false;
    }
    if (n === 2n) {
      return true;
    }
    if ((n % 2n) === 0n) {
      return false;
    }
    d = n - 1n;
    s = 0n;
    while ((d % 2n) !== 0n) {
      d = d / 2n;
      s = s + 1n;
    }
    
    nb = n.toString(2).length;
    r = (function() {
      var results = [];
      for (var i = 0; 0 <= k ? i < k : i > k; 0 <= k ? i++ : i--){ results.push(i); }
      return results;
    }).apply(this).map(function() {
      return gen_rand(nb - 1);
    });
    res = r.some(function(a) {
      var flg, pl;
      if (modular_exp(a, d, n) !== 1n) {
        pl = (function() {
          var results = [];
          for (var i = 0; 0 <= s ? i < s : i > s; 0 <= s ? i++ : i--){ results.push(i); }
          return results;
        }).apply(this).map(function(rr) {
          return (2n ** rr) * d;
        });
        flg = true;
        pl.forEach(function(p) {
          if (modular_exp(a, p, n) === 1n) {
            flg = false;
          }
        });
        if (flg) {
          return true;
        }
      }
    });
    return res === false;
  };

  // 素数生成
  gen_prime = function(bit) {
    var ret;
    while (true) {
      ret = this.gen_rand(bit);
      if (mr_primary_test(ret)) {
        break;
      }
    }
    return ret;
  };

}).call(this);