計算機科学のブログ

Building Abstractions with Functions - Functions and the Processes They Generate - Example: Testing for Primality - Probabilistic methods - Miller-Rabin test

Structure and Interpretation of Computer Programs: JavaScript Edition(Harold Abelson(著)、Gerald Jay Sussman(著)、Julie Sussman(著)、The MIT Press)のChapter 1(Building Abstractions with Functions)、1.2(Functions and the Processes They Generate)、1.2.6(Example: Testing for Primality)、Probabilistic methods、Exercise 1.28の解答を求めてみる。

コード

function square(x) {
    return x * x;
}
function is_even(n) {
    return n % 2 === 0;
}
function display(x) {
    console.log(x);
}
function math_floor(x) {
    return Math.floor(x);
}
function math_random() {
    return Math.random();
}
function expmod(base, exp, m) {
    function nontrivial_square_root_signal(n) {
        let r = square(n) % m;
        return n !== 1 && n !== m - 1 && r === 1 ?
            0 :
            r;
    }
    return exp === 0 ?
        1 :
        is_even(exp) ?
            nontrivial_square_root_signal(expmod(base, exp / 2, m)) :
            (base * expmod(base, exp - 1, m)) % m;
}

function miller_rabin_test(n) {
    function try_it(a) {
        return expmod(a, n, n) === a;
    }
    return try_it(1 + math_floor(math_random() * (n - 1)));
}
function fast_is_prime(n, times) {
    return times === 0 ?
        true :
        miller_rabin_test(n) ?
            fast_is_prime(n, times - 1) :
            false;
}
function is_prime(n) {
    return fast_is_prime(n, 10);
}

console.log('Carmichael numbers');
console.log(is_prime(561));
console.log(is_prime(1105));
console.log(is_prime(1729));
console.log(is_prime(2465));
console.log(is_prime(2821));
console.log(is_prime(6601));

console.log('素数');
console.log(is_prime(2));
console.log(is_prime(3));
console.log(is_prime(5));
console.log(is_prime(7));
console.log(is_prime(1009));

入出力結果(Terminal, Zsh)

% node answer1.28.js
Carmichael numbers
false
false
false
false
false
false
素数
true
true
true
true
true
%