何為Miller Rabin演算法 首先看一下度娘的解釋(如果你懶得讀直接跳過就可以反正也沒啥亂用:joy:) Miller-Rabin演算法是目前主流的基於概率的素數測試演算法，在構建密碼安全體系中占有重要的地位。通過比較各種素數測試演算法和對Miller-Rabin演算法進行的仔細研究，證明在電腦中構建 ...
何為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$，這個數也是合數(費馬小定理)
正確性
老祖宗告訴我們: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; }
