Rabin算法详解

何为Miller Rabin算法

首先看一下度娘的分解(纵然您懒得读直接跳过就能够反正也没啥乱用:joy:)

Miller-Rabin算法是这两天主流的依靠概率的素数测试算法,在塑造密码安全系统中据有主要的身份。通过相比较种种素数测试算法和对Miller-Rabin算法举办的精研,申明在微型计算机中创设密码安全体系时,
Miller-Rabin算法是大功告成素数测试的特级选项。通过对Miller-Rabin 算
法底层运算的优化,能够得到较往年促成更加好的质量。[1]  随着消息手艺的迈入、网络的普遍和电子商务的展开,
音讯安全稳步呈现出了其关键。消息的泄密、伪造、篡改
等主题素材会给新闻的官方具备者带来重大的损失。在Computer中创设密码安全系统可以提供4种最基本的保养音信安全的服
务:保密性、数据完整性、鉴定分别、抗抵赖性,从而能够很大程度上珍重用户的数额安全。在密码安全系统中,公开密钥
算法在密钥交流、密钥管理、居民身份评释等主题素材的处理上非常有效,由此在一切系统中据为己有首要的身份。近期的当众密钥
算法大多数依照大整数分解、有限域上的离散对数难题和椭
圆曲线上的离散对数难点,那一个数学难点的创设大多数都要求生成一种超大的素数,极其在杰出的猎豹CS6SA算法中,生成的素数的材质对系统的安全性有不小的熏陶。近来大素数的生
成,特别是专断大素数的成形主若是使用素数测试算法,本
文主要针对当前主流的Miller-Rabin 算法进行完善系统的分析和商讨,并对其落实进行了优化

简言之Miller
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)$

 

其一定律和素数判断有怎么着用吧?

首先,依照Miller 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;
}

相关文章