研讨会上的一群人Group of people at the seminar

本文将描述两种验证质数的方法，一种的增长率为 , 另外一种为probabilistic algorithms其增长率为logn.

寻找因子

寻找因子的方法简单而直接，从整数2开始，连续测试能否被整除，就是寻找第一个因子。

function square(x) {
    return x * x;
}

function smallest_pisor(n) {
    return find_pisor(n, 2);
}
function find_pisor(n, test_pisor) {
    return square(test_pisor) > n ? n
           : pides(test_pisor, n) ? test_pisor
           : find_pisor(n, test_pisor + 1);
}
function pides(a, b) {
    return b % a === 0;
}

smallest_pisor(42);

验证是否为质数，只需要验证，n是否与其最小的因子相等。

function is_prime(n) {
    return n === smallest_pisor(n);
}

函数find_pisor的最终测试条件，基于这样的事实，即如果n不是素数，那么它必然有因子小于或者等于 ,因此，我们的算法只需要验证1和之间的整数即可。因此，算法所执行步骤的增长率就是.

费马小定理

另外一种 乃是基于费玛小定理： 假如a是一个整数，p是一个質数，那么

实现的算法如下：

function is_even(n) {
    return n % 2 === 0;
}
​
function square(x) {
    return x * x;
}
​
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;
}
​
expmod(4, 3, 5);

这与之前的fast_expt方法极为相似。

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 random(n) {
    return Math.floor(Math.random() * n);
}
​
function fermat_test(n) {
    function try_it(a) {
        return expmod(a, n, n) === a;
    }
    return try_it(1 + random(n - 1));
}
​
console.log(fermat_test(97));
​

最后设置验证的次数。

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