Rabin算法详解

何为Miller Rabin算法

先是看一下度娘的解释(即使你懒得读直接跳过就可以反正也没啥乱用:joy:)

Miller-Rabin算法是当前主流的按照概率的素数测试算法,在构建密码安全部系中据为己有举足轻重的地位。通过相比各样素数测试算法和对Miller-Rabin算法进行的周密研商,申明在电脑中构建密码安全系统时,
Miller-Rabin算法是做到素数测试的极品选项。通过对米尔er-Rabin 算
法底层运算的优化,可以取得较以往落到实处更好的性能。[1]  随着新闻技术的前进、网络的推广和电子商务的进展,
新闻安全逐步突显出了其关键。音讯的泄密、伪造、篡改
等问题会给音信的官方拥有者带来紧要的损失。在电脑中构建密码安全部系可以提供4种最要旨的有限支撑音讯安全的服
务:保密性、数据完整性、鉴别、抗抵赖性,从而得以很大
程度上维护用户的数量安全。在密码安全系统中,公开密钥
算法在密钥调换、密钥管理、身份验证等题材的拍卖上无比有效,因而在所有连串中占有紧要的身份。近日的公开密钥
算法超过半数根据大整数分解、有限域上的离散对数问题和椭
圆曲线上的离散对数问题,这么些数学难题的构建大多数都须求生成一种超大的素数,越发在经典的RSA算法中,生成的素数的质量对系统的安全性有很大的影响。如今大素数的生
成,尤其是随便大素数的转移紧即使接纳素数测试算法,本
文紧要针对当下主流的米尔er-Rabin 算法进行宏观系统的分析
和商量,并对其落到实处进行了优化

大约米尔er
Rabin算法在音信学奥赛中的应用就一句话:

看清一个数是不是是素数

定理

Miller
Rabin算法的根据是费马小定理:

$$a^{p-1}\equiv 1\left(
modP\right)$$

证明:

性能1:$p-1$个整数$a,2a,3a,…(p-1)a$中尚无一个是$p$的翻番 

特性2:$a,2a,3a,…(p-1)a$中没有其余四个同余与模$p$的

因而$a,2a,3a,…(p-1)a$对模$p$的同余既不为零,也从未五个同余等同

据此,那$p-1$个数模$p$的同余一定是$a,2a,3a,…(p-1)a$的某一种排列

即$a,2a,3a,…(p-1)a \equiv
{1,2,3,…,p-1}! (mod p)$

化简为

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

基于Wilson定理可见$(p-1)!$与$p$互质,所以还要约去$(p-1)!$

即得到$a^{p-1}\equiv 1\left(
modP\right)$

 

那么是否当一个数$p$满意任意$a$使得$a^{p-1}\equiv
1\left( modP\right)$成立的时候它就是素数呢?

在费马小定理被认证后的很长一段时间里,人们都认为这是很明确的,

皇冠直营现金网官方网,只是到底有一天,人们给出了反例 ,推翻了这些结论

 

那是否代表利用费马小定理的思索去看清素数的思索就是谬误的吗?

答案是毫无疑问的。

然则如若我们可以人工的把出错率降到分外小吗?

诸如,对于一个数,大家有$99.99999$%的几率做出正确判断,那那种算法不也很优越么?

 

于是Miller Rabin算法诞生了!

 

首先介绍一下二次探测定理

若$p$为素数,$a^{2}\equiv 1\left(
modP\right)$,那么$a\equiv \pm 1\left( modP\right)$

证明

$a^{2}\equiv 1\left(
modP\right)$

$a^{2}-1\equiv 0\left(
modP\right)$

$(a+1)*(a-1)\equiv 0\left(
modP\right)$

那么

$(a+1)\equiv 0\left(
modP\right)$

或者

$(a-1)\equiv 0\left(
modP\right)$

(此处可依照唯一分解定理讲明)

$a\equiv \pm 1\left(
modP\right)$

 

其一定律和素数判定有啥用吧?

首先,根据米尔(Mill)er Rabin算法的长河

若是需求判定的数是$p$

(博主乱入:以下内容较肤浅,请密切精晓:joy:)

我们把$p-1$分解为$2^k*t$的形式

然后轻易拔取一个数$a$,统计出$a^t mod
p$

让其相连的$*2$,同时结合二次探测定理举办判定

如果我们$*2$后的数$mod p ==
1$,然而从前的数$mod p != \pm 1$

那么这么些数就是合数(违背了二次探测定理)

诸如此类乘$k$次,最终取得的数就是$a^{p-1}$

那就是说只要最后总计出的数不为$1$,这些数也是合数(费马小定理)

正确性

开拓者告诉我们:joy::若$p$通过一次测试,则$p$不是素数的几率为$25$%

这就是说通过$t$轮测试,$p$不是素数的概率为$\dfrac
{1}{4^{t}}$

自身习惯用$2,3,5,7,11,13,17,19$那多少个数举办判定

在音讯学范围内出错率为$0$%(不带高精:joy:)

code

留神在展开素数判断的时候必要利用快捷幂。。

本条应该相比较不难,就不细讲了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define LL long long 
using namespace std;
const LL MAXN=2*1e7+10;
const LL INF=1e7+10;
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline LL read()
{
    char c=nc();LL x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    return x*f;
}
LL fastpow(LL a,LL p,LL mod)
{
    LL base=1;
    while(p)
    {
        if(p&1) base=(base*a)%mod;
        a=(a*a)%mod;
        p>>=1;
    }
    return base;
}
LL num[]= {2,3,5,7,11,13,17,19};
bool Miller_Rabin(LL n)
{
    if (n==2) return 1;
    if((n&1)==0||n==1) return false;
    for (LL i=0; i<8; i++) if (n==num[i]) return 1;

    LL temp=n-1,t=0,nxt;
    while((temp&1)==0) temp>>=1,t++;

    for(LL i=0;i<8;i++)
    {
        LL a=num[i];
        LL now=fastpow(a,temp,n);
        nxt=now;
        for(LL j=1;j<=t;j++)
        {
            nxt=(now*now)%n;
            if(nxt==1&&now!=n-1&&now!=1) return false;
            now=nxt;
        }
        if(now!=1) return false;
    }
    return true;
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif 
    LL N=read(),M=read();
    while(M--)
    {
        LL opt=read();
        if(Miller_Rabin(opt))    printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

相关文章