Miller_Rabin

$Miller$_$Rabin$

理论基础

费马小定理：$a^{p-1}\equiv 1(\mod p)$

证明如下:考虑$1,2,3,...,p-1$这$p-1$个数字，同时乘$a$，得到$a,2a,3a,...,(p-1)a$

$\because a \equiv b (\mod p),\gcd(c,p)=1$

$\therefore ac\equiv bc(\mod p)$

$\therefore \prod\limits_{i=1}^{p-1}i\equiv\prod\limits_{i=1}^{p-1}(i*a)(\mod p)$

$\therefore (p-1)!\equiv (p-1)! a^{p-1}(\mod p)$

$\because \gcd ((p-1)!,p) = 1$

$\therefore a^{p-1} \equiv 1(\mod p)$

（第三行成立是因为两边同为mod p的一个完全剩余系）

二次探测 ： $p\in prime\And0<x<p$，则方程$x^2 \equiv 1(\mod p)$的解为$x=1$或$x=p-1$

证明如下：

$\because x^2 \equiv 1 (\mod p)$

$\therefore x^2-1 \equiv 0 (\mod p)$

$\therefore p|(x-1)(x+1)$

$\because p \in prime$

$\therefore x=1||x=p-1$

算法流程

(1) 特判出一定的合数和素数；

(2)设测试的数为$x$,取质数$a$，设$s,k$,满足$a^s*k=x-1$；

(3)计算出$a^t$，然后不断地平方并且进行二次探测(k次)；

(4)根据费马小定理，如果最后$a^{x-1}\not\equiv 1(\mod x)$，则说明$x$为合数；

(5)多次取不同的a进行测试（a可以为指定质数，也可以为$rand()\%(x-1)+1$

代码实现

以下代码是与随机化无关的$miller $_ $rabin$

/*
 * @Author: luxin 
 * @Date: 2020-02-07 14:18:35 
 * @Last Modified by: luxin
 * @Last Modified time: 2020-02-07 14:32:46
 */
typedef long long ll;
const ll p[]={2,3,5,7,11,13,17,19};
ll qpow(ll x,ll a,ll mod){
    __int128 ans=1;
    for(;a;a>>=1,x=((__int128)x)*x%mod);
        if(a&1)ans=ans*x%mod;
    return ans;
}
bool miller_rabin(ll x){
    if(x==2||x==3||x==5||x==7||x==11||x==13||x==17||x==19)return 1;
    if(x%2==0||x%3==0||x%5==0||x%7==0||x%9==0||x%11==0||x%13==0||x%17==0||x%19==0)return 0;
    ll t=x-1;int k;
    for(k=0;!(t&1);t>>=1,++k);
    for(int i=0;i<8;++i){
        ll a=p[i];;
        ll last=qpow(a,t,x);
        for(int j=1;j<=k;++j)
        {
            ll now=(__int128)last*last%x;
            if(now==1&&last!=x-1&&last!=1)return 0;
            last=now;
            if(now==1)break;
        }
        if(last!=1)return 0;
    }
    return 1;
}