首页 > 分享 > Miller Rabin判断素数

Miller Rabin判断素数

萌宠菠菠乐园
2024-09-23 04:02

M i l l e r R a b i n Miller Rabin Miller Rabin判断素数

前置知识：

1.费马小定理： a p − 1 ≡ 1 ( m o d p ) ， p a^{p-1}equiv 1 pmod p，p ap−1≡1(modp)，p为质数，且 a a a不为 p p p倍数。

2.二次探测定理：
p p p为素数，则 x 2 ≡ 1 ( m o d p ) x^2equiv 1pmod p x2≡1(modp)的解为： x 1 = 1 , x 2 = p − 1 x_1=1,x_2=p-1 x1=1,x2=p−1。

算法实现流程：

1.特判，当 n < 3 n<3 n<3直接特判，否则 n n n为偶数肯定不是。

2.显然由1筛出来的情况 n − 1 n-1 n−1肯定是偶数了。
令 p = n − 1 = x × 2 c p=n-1=xtimes 2^c p=n−1=x×2c。

3.接下来我们需要利用二次探测定理，选取一个底数 a a a，然后先计算出 a p a^p ap，这里形式就变成了 a p = a n − 1 = a x × 2 c = ( a x ) 2 c a^p=a^{n-1}=a^{xtimes 2^c}=(a^x)^{2^c} ap=an−1=ax×2c=(ax)2c，然后我们需要循环判断 c c c次，是否满足二次探测定理。

令 x = a x ( m o d n ) , y = x x=a^xpmod{n},y=x x=ax(modn),y=x
每次 x = x × x ( m o d n ) = x 2 ( m o d n ) x=xtimes xpmod{n}=x^2pmod{n} x=x×x(modn)=x2(modn)

然后特判： y 2 = x y^2=x y2=x，当 x = 1 x=1 x=1时 y y y是否为 1 1 1或 n − 1 n-1 n−1。

然后一轮过后 y = x y=x y=x，进入下一轮。

4.最后 x = a n − 1 x=a^{n-1} x=an−1，利用费马小定理特判 x = 1 x=1 x=1即可。

通过多次测试，使随机算法的错误概率降到很小。

时间复杂度： O ( k l o g 3 n ) O(klog^3n) O(klog3n)， k k k为测试次数。

例题：

传送门

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a,b) memset(a,b,sizeof a) #define PII pair<int,int> #define fi first #define se second #define pb push_back ll qmul(ll a,ll b,ll mod){return (ll)(__int128(a)*b%mod); } ll qmul1(ll a,ll b,ll mod){ll t=a*b-(ll)((long double)a/mod*b+0.5)*mod;return t<0?t+mod:t; } ll ksm(ll a,ll n,ll mod){ll ans=1;while(n){if(n&1) ans=qmul1(ans,a,mod);a=qmul1(a,a,mod);n>>=1;}return ans; } ll d[8]={2,3,5,7,11,13,79,97}; bool fun(ll n){if(n<3) return n==2;if(n%2==0) return 0;ll p=n-1,c=0;while(p%2==0) p>>=1,c++;for(int i=0;i<8;i++){if(d[i]==n) return 1;ll x=ksm(d[i],p,n),y=x;for(int j=0;j<c;j++){x=qmul1(x,x,n);if(x==1&&!(y==1||y==n-1)) return 0;y=x;}if(x!=1) return 0;}return 1; } int main(){ll x;while(~scanf("%lld",&x)){puts(fun(x)?"Y":"N");}return 0; }

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647