帮你精通JavaScript：费马小定理验证质数

费马小定理应用“模除”验证是否为质数：

假如p是一个质数，a是一个小于p整数，那么：

首先要构造“模除”函数如下：

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 square(x) {
    return x * x;
}

function is_even(n) {
    return n % 2 === 0;
}

然后测试的随机数：

function random(n) {
    return Math.floor(Math.random() * n);
}

定义费马小定理：

function fermat_test(n) {
		let a = 1 + random(n - 1));
    return expmod(a, n, n) === a;
}

最后测试：

function fast_is_prime(n, times) {
    return times === 0 ? true
           : fermat_test(n) ? fast_is_prime(n, times - 1)
           : false;
}

验证结果如下：