Rabin算法详解

何为Miller Rabin算法

首先看一下度娘的表达(要是您懒得读直接跳过就能够反正也没啥乱用:joy:)

Miller-Rabin算法是近来主流的基于可能率的素数测试算法,在创设密码安全系统中占有主要的身价。通过相比各个素数测试算法和对Miller-Rabin算法实行的精心研讨,评释在总括机中构建密码安整种类时,
Miller-Rabin算法是实现素数测试的最佳选拔。通过对Miller-Rabin 算
法底层运算的优化,能够博得较往年贯彻更好的属性。[1]  随着音讯技术的发展、互连网的普及和电子商务的展开,
消息安全稳步呈现出了其首要。消息的泄密、伪造、篡改
等难题会给消息的合法拥有者带来主要的损失。在处理器中构建密码安全部系能够提供4种最基本的护卫消息安全的服
务:保密性、数据完整性、鉴定区别、抗抵赖性,从而能够相当大程度上保险用户的数码安全。在密码安全部系中,公开密钥
算法在密钥交换、密钥管理、身份表明等难题的处理上最好有效,因而在一切系统中据为己有相当重要的身价。如今的当众密钥
算法一大半基于大整数分解、有限域上的离散对数难点和椭
圆曲线上的离散对数难点,这么些数学难点的创设半数以上都需求生成一种超大的素数,特别在经典的奥迪Q7SA算法中,生成的素数的品质对系统的安全性有一点都不小的影响。如今大素数的生
成,特别是随意大素数的变型主假若应用素数测试算法,本
文首要针对如今主流的Miller-Rabin 算法进行完善系统的辨析
和钻研,并对其促成实行了优化

粗略Miller
Rabin算法在消息学奥赛后的应用就一句话:

看清二个数是或不是是素数

何为Miller Rabin算法

第贰看一下度娘的诠释(借使您懒得读直接跳过就可以反正也没啥乱用:joy:)

Miller-Rabin算法是眼下主流的遵照可能率的素数测试算法,在营造密码安全部系中占有主要的地位。通过相比较种种素数测试算法和对Miller-Rabin算法进行的密切钻探,注脚在微型计算机中创设密码安全系统时,
Miller-Rabin算法是成就素数测试的极品选项。通过对Miller-Rabin 算
法底层运算的优化,可以获取较往年落到实处更好的属性。[1]  随着新闻技术的发展、网络的普及和电子商务的展开,
音讯安全逐步突显出了其重庆大学。消息的泄密、伪造、篡改
等题材会给音讯的官方拥有者带来重庆大学的损失。在计算机中营造密码安全系统能够提供4种最主题的掩护音信安全的服
务:保密性、数据完整性、鉴定识别、抗抵赖性,从而得以非常大程度上保护用户的多寡安全。在密码安全系统中,公开密钥
算法在密钥沟通、密钥管理、身份表明等题材的拍卖上非常有效,由此在任何种类中据为己有相当重要的地位。近日的公然密钥
算法当先1/4基于大整数分解、有限域上的离散对数难题和椭
圆曲线上的离散对数难题,这一个数学难点的营造一大半都须求生成一种超大的素数,特别在经典的PRADOSA算法中,生成的素数的品质对系统的安全性有极大的震慑。近年来大素数的生
成,越发是随便大素数的变型主假使采取素数测试算法,本
文主要针对当下主流的Miller-Rabin 算法进行完善系统的剖析
和斟酌,并对其落实实行了优化

一句话来说Miller
Rabin算法在新闻学奥赛后的应用就一句话:

判定二个数是或不是是素数

定理

米尔er
Rabin算法的依照是费马小定理:

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

证明:

属性1:$p-1$个整数$a,2a,3a,…(p-1)a$中从未3个是$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$%的概率做出正确判断,这那种算法不也很优越么?

 

于是米尔er 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$的形式

下一场轻易挑选3个数$a$,计算出$a^t mod
p$

让其相连的$*2$,同时结合叁次探测定理实行判定

借使我们$*2$后的数$mod p ==
1$,不过在此以前的数$mod p != \pm 1$

那么那几个数正是合数(违背了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$成立的时候它便是素数呢?

在费马小定理被证实后的不短一段时间里,人们都觉得那是很醒目标,

只是终究有一天,人们给出了反例 ,推翻了这一个结论

 

那是还是不是意味利用费马小定理的想念去判断素数的思索就是一无可取的啊?

答案是一定的。

而是倘若我们能够人工的把出错率降到一点都十分的小吗?

比如说,对于3个数,大家有$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$

让其持续的自乘,同时结合3次探测定理实行判定

一旦咱们自乘后的数$\pmod p =
1$,可是在此以前的数$\pmod p \not = \pm 1$

那么那些数正是合数(违背了壹次探测定理)

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

那么一旦最后总结出的数不为$1$,那么些数也是合数(费马小定理)

正确性

老祖宗告诉大家:joy::若$p$通过2次测试,则$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");
}

 

相关文章