数论 Miller_Rabin质数测试

作用

当需要判断一个数字是否是质数时，又发现数字过大，(0(sqrt n))难以承受的时候，就可以使用Miller_Rabin质数测试

基本定理

定理一,费马小定理：

定理二，二次探测：

基本定理的证明

直接引用一下别人博客上的证明，感觉证明得清晰明了，个人复述一下反而显得累赘

至此，是Miller_Rabin所需要的所有理论知识

算法流程

设要测试的数字为x

1. 若x是偶数，0，1，2，可以直接判断
2. 找出如下形式的s，t，使之满足(2^stimes tequiv1 (mod x)),要求t是个奇数
3. 随机质数a(满足a小于x)
4. 对于(a^t)循环进行：平方、二次探测..（共计循环s次）。倘若任意一次不满足条件，则x为合数
5. 对于((2^{t})^{2times s})验证费马小定理，倘若不满足，则x为合数
6. 循环随机若干个质数a，继续测试
7. 上述操作之后仍未筛掉x，则x大概率是质数

Tips

[1] Miller_Rabin质数测试可以极大概率地判断出质数，但存在会有合数误判为质数的情况。这类强伪质数，称之为卡米歇尔强伪素数。

[2] 虽然是大概率，但概率之大足以放心使用。据考证：在int范围内，取遍30以内的所有质数后，保证该算法的正确性

[3] Miller_Rabin可以承受高达long long的数据范围，实际上限未知

[4] 记得快速乘优化

code:

bool millar_rabin(ll x){
    if(x==2) return true;
    if(!(x&1)||x==0||x==1) return false;
    ll s=0,t=x-1;
    while(!(t&1)) s++,t>>=1;  //寻找合适的s和t

    for(int p=1;p<=30&&prime[p]<x;++p){
        ll b=qsm((ll)prime[p],t,x),k;
        for(ll i=1;i<=s;++i){
            k=qsc(b,b,x);  //将b平方
            if(k==1&&b!=1&&b!=x-1) return false;
            b=k;
        }
        if(b!=1) return false;
    }
    return true;
}

参考资料：Miller-Rabin素数测试算法