Miller Rabin算法详解。Miller Rabin算法详解。

何为Miller Rabin算法

先是看一下度娘的说明(如果你懒得读直跨越了就足以反正也从没啥乱用:joy:)

Miller-Rabin算法是当前主流的基于概率的素数测试算法,在构建密码安全系统中占据主要之位置。通过比各种素数测试算法和指向Miller-Rabin算法进行的缜密研究,证明在计算机被构建密码安全体系时,
Miller-Rabin算法是得素数测试的超级选项。通过对Miller-Rabin 算
法底层运算的优化,可以收获比较以往贯彻再好之属性。[1]  随着信息技术的前进、网络的推广和电子商务的拓展,
信息安全逐步显示出了彼要。信息的泄密、伪造、篡改
等问题会给信息的官拥有者带来重要的损失。在处理器被构建密码安全系可以提供4栽最基本的保护信息安全之服
务:保密性、数据完整性、鉴别、抗抵赖性,从而可以好大
程度达护用户之多寡安全。在密码安全体系中,公开密钥
算法在密钥交换、密钥管理、身份证明等问题之处理上最好有效,因此当普系统中据为己有重要之地位。目前之公开密钥
算法大部分基于大整数分解、有限域上之离散对数问题和椭
圆曲线上之离散对数问题,这些数学难题的构建大部分且需
要十分成一种超大的素数,尤其以藏的RSA算法中,生成的素数的身分对系的安全性产生良死的震慑。目前大素数的生
成,尤其是不管三七二十一大素数的变迁主要是采取素数测试算法,本
文主要针对当下主流的Miller-Rabin 算法进行完美系统的分析
和研讨,并针对那个实现进行了优化

说白了Miller
Rabin算法betway必威足彩在信息学奥赛中之应用就是相同句话:

判定一个往往是否是素数

何为Miller Rabin算法

先是看一下度娘的诠释(如果你懒得读直跨越了就好反正也并未啥乱用:joy:)

Miller-Rabin算法是眼下主流的根据概率的素数测试算法,在构建密码安全系受到占举足轻重的身价。通过比较各种素数测试算法和针对Miller-Rabin算法进行的周密研究,证明在电脑中构建密码安全系统时,
Miller-Rabin算法是得素数测试的特等选项。通过对Miller-Rabin 算
法底层运算的优化,可以获比较以往实现还好的性能。[1]  随着信息技术之进步、网络的普及与电子商务的拓,
信息安全逐步显示有了该主要。信息之泄密、伪造、篡改
等题材会见给信息之官方拥有者带来重要的损失。在电脑中构建密码安全系统可以提供4种植最核心的护信息安全的服
务:保密性、数据完整性、鉴别、抗抵赖性,从而得以老大
程度上保障用户的数据安全。在密码安全体系受到,公开密钥
算法在密钥交换、密钥管理、身份验证等问题之拍卖及极其有效,因此当全体系中据为己有重要的地位。目前之公开密钥
算法大部分基于大整数分解、有限域上之离散对数问题和椭
圆曲线上之离散对数问题,这些数学难题的构建大部分且需
要非常成一种植超大的素数,尤其当经的RSA算法中,生成的素数的成色对系统的安全性产生良要命之震慑。目前大素数的生
成,尤其是不管三七二十一大素数的变化主要是行使素数测试算法,本
文主要针对当下主流的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)$

冲威尔逊定律可知$(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$,这个累为是合数(费马小定理)

定理

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

$$a^{p-1}\equiv 1 \pmod P$$

证明:

性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)} \pmod p$

化简为

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

依据威尔逊定律可知$(p-1)!$与$p$互质,所以还要横去$(p-1)!$

即得到$a^{p-1}\equiv 1 \pmod P$

 

那是免是当一个数$p$满足任意$a$使得$a^{p-1}\equiv
1 \pmod P$成立之时段她就是素数呢?

于费马小定理被证明后的挺丰富一段时间里,人们都觉着这是很明白的,

唯独毕竟发生同一天,人们为闹了反例 ,推翻了此结论

 

立即是否意味着利用费马小定理的思考去判断素数的思量就是不当的吗?

答案是必之。

然要是我们可人工的把出错率降到十分小吗?

准,对于一个往往,我们出$99.99999$%底几乎带领做出正确判断,那这种算法不为特别美妙越么?

 

乃Miller Rabin算法诞生了!

 

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

若$p$为素数,$a^{2}\equiv 1 \pmod
P$,那么$a\equiv \pm 1 \pmod P$

证明

$a^{2}\equiv 1 \pmod P$

$a^{2}-1\equiv 0 \pmod P$

$(a+1)*(a-1)\equiv 0 \pmod P$

那么

$(a+1)\equiv 0 \pmod P$

或者

$(a-1)\equiv 0 \pmod P$

(此处可因唯一分解定理证明)

$a\equiv \pm 1 \pmod P$

 

其一定律和素数判定来什么用为?

率先,根据Miller Rabin算法的历程

假使需要判定的累是$p$

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

当$a$是素数,有$a ^ {2^k * t} \equiv 1
\pmod p$

然后轻易挑选一个数$a$,计算出$a^t \pmod
p$

吃其持续的自乘,同时整合二次于探测定理进行判定

若我们自乘后底数$\pmod p =
1$,但是之前的数$\pmod p \not = \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:)

正确性

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

那么通过$t$轮测试,$p$不是素数的几率为$\dfrac
{1}{4^{t}}$

自我习惯用$2,3,5,7,11,13,17,19$这几只数进行判断

以信息学范围外出错率为$0$%(不带大精)

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;
}

code

顾在进展素数判断的时节用使用快速幂。。

这理应比较简单,就非细讲了

#include<cstdio>
#define LL long long 
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, Test[10] = {2, 3, 5, 7, 11, 13, 17};
int pow(int a, int p, int mod) {
    int base = 1;
    for(; p; p >>= 1, a = (1ll * a * a) % mod) 
        if(p & 1) base = (1ll * base * a) % mod;
    return base % mod;
}
bool Query(int P) {
    if(P == 1) return 0;
    int t = P - 1, k = 0;
    while(!(t & 1)) k++, t >>= 1;
    for(int i = 0; i < 4; i++) {
        if(P == Test[i]) return 1;
        LL a = pow(Test[i], t, P), nxt = a;
        for(int j = 1; j <= k; j++) {
            nxt = (a * a) % P;
            if(nxt == 1 && a != 1 && a != P - 1) return 0;
            a = nxt;
        }
        if(a != 1) return 0;
    }
    return 1;
}
main() { 
    N = read(); M = read();    
    while(M--) puts(Query(read()) ? "Yes" : "No");
}

 

相关文章