miller rabin

前置

朴素素性检验

从 试到 , 如果可以被整除，则为合数；否则为素数

Fermat小定理

为素数，则 有

Fermat素性检验

在 中选取几个数，利用Fermat小定理快速幂计算，如果结果不为1，则一定不是素数，否则大概率是素数。

Carmichael Number

也称 Fermat 伪素数，即满足 的合数，如

二次探测定理

为奇素数，则的解为

miller rabin

在满足 时 可能为合数，那么通过二次探测定理,可以将 除以 , 进一步判断其是否满足开根后结果为 , 来判断其是否为素数。

取 , 则 为偶数

先判断 是否成立，如果不成立则为合数。

然后将 , 如果 不等于 , 则为合数

直到 为奇数或 , 如果 不成立则为合数，否则大概率为素数

code:

int miller_rabin(int a,int p){
    int d=p-1;
    if(kp(a,d,p)!=1) return 0;
    while(d){
        int cur=kp(a,d,p);
        if(cur!=1 && cur!=p-1) return 0;
        if((d&1) || cur==p-1) return 1;
        d>>=1;
    }
    return 1;
}

其中 表示求

如果是素数，最终的 序列应该为 或

单次检验复杂度为 , 次测验为

• 注：这里的复杂度 其实并不准确，没有考虑大数乘法，事实上大数乘法需要用到FFT加速才能达到比较好的效果

对于 以内数选取 为底数，可以确定性判素

对于 以内，选取前 个素数

miller rabin 的出错率

定理1

如果 是有限群 的一个真子群，那么

此为Lagrange定理的一个推论(如果 是有限群 的一个真子群，那么 是 的约数)

证明略

定理2

如果 是奇合数，则 为合数的证据数目至少为

这里证据指满足 的

证明：

我们要证明非证据一定是 的成员 ( 指 到 的整数)

因为非证据 满足 , 这说明 这个方程有解

根据裴蜀定理， 方程才有解，则

这说明 是 的成员

进一步，我们要说明所有非证据包含在 的一个真子群 中

因为 ,

由定理1，我们有

即非证据数目最多为 , 则证据数目最少为

具体是可以找出这样的真子群 的，参见算法导论

结论

miller rabin 算法的出错率由测验次数 决定，概率最大为

证明：

对于要验证的数 , 它是合数的证据至少为 , 所以验出他是合数的概率最少为

由于进行了 轮，所以全部不能验出他是合数的概率最大为 , 即一次都没能发现他是合数

Lucas sequence

另一种素数测验法，与miller rabin结合后为Baillie-PSW Test，是非常强大的Probable prime test

ECPP

椭圆曲线