Miller-Rabin素数测试算法

已知费马定理 p 是素数

$a ^ {p -1} = 1 \pmod p \tag{F}$ 那么他的逆命题,如果上面式子,$p$ 是否是素数呢?
答案是否定的,但是我们可以通过不同的 $a$ 来测试来增加我们的确信度。

但是，如果$p$很大,每次更换 $a$ 重新计算$a ^ {p-1}$ 代价有点大，科学家想到了加速办法。

二次探测

如果 p 是素数

$x ^2 = 1 \pmod p$ 的解只有 $1,p-1$ $x_1 = 1 \pmod p \\ x_2 = -1 \pmod p$

有什么用?

看到2次方了吗,这个我们可以利用起来逐级降次(逐次开方),或者自底向上逐渐升次。

对于每个＞2的素数, $p-1 = 2 ^ k \times s$ 测试

随机选取一个数 $a < p$;
计算初始值 $x = a ^ s \pmod{p}$
1. 如果 $x = 1 \quad 或者 \quad x = p-1 \quad 即x= -1 \pmod p$ ，说明肯定满足 $a^p-1 = 1 \pmod p$ ,后面继续平方结果肯定也是1,那么通过测试。
2. 如果 $x \not =\pm1 \pmod p$ 那么逐次升幂测试(最多$k$次,不能超过 $a^{p-1}$),后面还有机会通过。
  1. StepA:$x = x ^ 2 \pmod p$
    - 如果 $x \not =\pm1 \pmod p$ ,继续步骤StepA,但是总平方次数不能超过 $k$次
    - 如果 $x =\pm1 \pmod p$,那么通过测试。
如果总的平方次数到 $k$次了,依然没有通过,那么,这就是个合数,中断
根据需要,如果需要增加可信度,再走一次步骤1

例子

我们检验 $p = 541$
$p -1 = 2 ^ 2 * 135$

随机选择 a = 154
1. $a ^ {135} \pmod{541} = 540$ 通过
随机 a = 2
1. $a ^ {135} \pmod{541} = 52$
2. $52 ^ 2 \pmod{541} = 540$ 通过
随机 a = 19
1. $a ^ {135} \pmod{541} = 540$ 通过

…

下面是计算 1000以内的素数个数 ,只是原理验证,类型用的 JavaScript 内建的Number,大小有限制

function isPrime(p){
    if (p < 2) {
        return false;
    }
    function testPrime( a,p){
        
        /**
         * 计算 a ^2^k mod p
         */
        function pow(a,k,p){
            var z = 0
            while(z ++  < k){
                a = a * a %p
            }
            return a ;
        }

        /**
         * 计算 arr[0] * arr[x] mod p
         */
        function mods(p,arr){
            var z = arr[0] % p;
            for (let index = 1; index < arr.length; index++) {  
                const element = arr[index]; 
                z = z * element % p
            }
            return z;
        }

 
        // 分解 p-1 = 2 ^K  * s
        var p_1 = p-1;
        var s = 1;
        var K = 0;
        var rightShift = 0;
        while((p_1 >>rightShift & 1) == 0 && (p_1 >>rightShift)){
            rightShift ++ ;
        }
        s = p_1 >> rightShift;
        K = rightShift;


        /// 分解 s = 2 ^x1 + 2 ^x2 ...
        /// 直接读取二进制位
        var m = [];
        var k0 = 0 ,tmp = s;
        while(tmp > 0 ){
            const z = tmp & 1;
            if (z) {
                m.push(pow(a,k0,p));
            }
            k0 ++ ;
            tmp = tmp >> 1;
        }


        // 计算 ss = a ^s
        var ss = mods(p,m);
        // 逐步测试 ss ^2  = 1 ,-1 mod p
        while (ss !== 1 && ss !== p_1 && K -- > 0){
            ss = ss * ss % p;
        }
        return ss == 1 || ss == p_1  
    }
    this.testPrime = testPrime;


    if (!p) {
        return false;
    }
    /**
     * 使用这些数作为测试数,出错概率几乎为0
     *   3,825,123,056,546,413,051 是第一个反例,伪证
     */
    var testNumbers = [2,3,5,7,11,13,17,19,23]
    for (let index = 0; index < testNumbers.length  ; index++) {
        var  a =   testNumbers[index];
        const testResult = testPrime(a,p);
        if(!testResult){
            // console.log('测试不通过',`${a } ${p }  ${testResult}`);
            return false;
        }
    }
    return true;
}

module.exports = isPrime


// var c = 0,p = 1;
// var arr = []
// while(p++ < 10000){
//     if(isPrime(p)){
//         c ++ ;
//         arr.push(p);
//     }
// }
 
// console.log(c);

看到AKS算法,也是多项式时间,但是是确定性的算法。AKS

L 记事本

Miller-Rabin素数测试算法

Miller-Rabin素数测试算法

二次探测

例子