Magicode
0

# 高速指数演算と素数判定

// 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);