計算機科学のブログ

Building Abstractions with Functions - Functions and the Processes They Generate - Example: Testing for Primality - Probabilistic methods - Carmichael numbers, Fermat 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.27の解答を求めてみる。

コード

function square(x) {
    return x * x;
}
function is_even(n) {
    return n % 2 === 0;
}
function expmod(base, exp, m) {
    return exp === 0 ?
        1 :
        is_even(exp) ?
            square(expmod(base, exp / 2, m)) % m :
            (base * expmod(base, exp - 1, m)) % m;
}
function carmichael_test(n) {
    function try_it(a) {
        return expmod(a, n, n) === a;
    }
    function iter(a) {
        return a === n ?
            true :
            try_it(a) ?
                iter(a + 1) :
                false;
    }
    return iter(2);
}

console.log(carmichael_test(4));
console.log(carmichael_test(6));
console.log(carmichael_test(8));
console.log(carmichael_test(9));
console.log(carmichael_test(10));
console.log(carmichael_test(12));

console.log('*****');

console.log(carmichael_test(561));
console.log(carmichael_test(1105));
console.log(carmichael_test(1729));
console.log(carmichael_test(2465));
console.log(carmichael_test(2821));
console.log(carmichael_test(6601));

入出力結果(Terminal, Zsh)

% node answer1.27.js
false
false
false
false
false
false
*****
true
true
true
true
true
true
%