何為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 \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$的形式
當$p$是素數，有$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$，這個數也是合數(費馬小定理)
正确性
老祖宗告訴我們，若$p$通過一次測試，則$p$不是素數的機率為$25$%
那麼經過$t$輪測試,$p$不是素數的機率為$\dfrac {1}{4^{t}}$
我習慣用$2,3,5,7,11,13,17,19$這幾個數進行判斷
在資訊學範圍内出錯率為$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");
} 作者：自為風月馬前卒
個人部落格http://attack204.com//
出處：http://zwfymqz.cnblogs.com/
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。