Miller Rabin素数测试 复习小记

Preface

为什么是复习小记?因为忘了个精光QAQ

Miller Rabin

素数测试基于以下两个原理:

费马小定理

(a,p)=1 p 是质数,则 ap11 (mod p) 反之不一定成立

二次探测定理

p 是素数,则 x21 (mod p) 的解只有 x=1 x=p1(1)
也即如果 x21 (mod p) x1,xp1 ,则 p 必定是合数

步骤

  1. p1=2tu
  2. 随机一个 a[2,p1]
  3. x=au 开始对 x 平方 t 次。同时对 x 检验二次探测定理。
  4. 最后检验 x 是否等于 1 (费马小定理),并回到操作2执行多次

板子

bool check(ll n,ll p,ll u,ll t)
{
    ll x=qmi(n,t,p);
    fo(i,1,u)
    {
        ll nxt=qmul(x,x,p);
        if(nxt==1 && x!=1 && x!=p-1) return 0;
        x=nxt;
    }
    return x==1;
}
bool miller_rabin(ll p)
{
    if(p==2) return 1;
    if(p<2 || !(p&1)) return 0;
    ll u=0,t=p-1;
    for(;t%2==0;t/=2) u++;
    fo(i,1,10)
    {
        ll n=rand()%(p-2)+2;
        if(!check(n,p,u,t)) return 0;
    }
    return 1;
}
相关文章
相关标签/搜索