算法思想
對于大于2的素數(shù)n丸相，將n-1拆分為
對于待測數(shù)n灭忠，當找到的a不符合上述條件膳算，那么稱a為一個"witness for the compositeness of n"，且n一定是一個合數(shù)弛作。否則稱a為一個"strong liar"涕蜂，且n是一個基于a的"strong probable prime"。
準確性
所有的奇合數(shù)都有很多的a滿足"witness"的條件映琳，不過目前為止還沒有確定的算法能夠直接根據(jù)n生成這樣的數(shù)a机隙，于是我們可以多次隨機抽取1~n-1中的整數(shù)并做測試。
當我們k次隨機選取a測試時萨西，一個合數(shù)被該算法判定為素數(shù)的概率是4^(-k)有鹿。
一種實現(xiàn)
#include <iostream>
#include <cstdlib>
using namespace std;
typedef long long ll;
ll mod_pow(ll x, ll y, ll m) {
ll base = x, res = 1;
while (y) {
if (y&1) (res*=base)%=m;
(base*=base)%=m;
y>>=1;
}
return res;
}
bool MillerRabin(ll n, int k) {
if (n==2||n==3||n==5||n==7||n==11||n==13) return true;
if (n==1||n%2==0||n%3==0||n%5==0||n%7==0||n%11==0||n%13==0) return false;
ll d=n-1;
int r=0;
while (d%2==0) {
d>>=1;
++r;
}
for (int i=0;i<k;++i) {
ll a=rand()%(n-2)+2;
ll x=mod_pow(a,d,n);
bool flag = false;
if (x==1||x==n-1) continue;
for (int j=0;j<r-1;++j) {
x=mod_pow(x,2,n);
if (x==1) return false;
if (x==n-1) {
flag=true;
break;
}
}
if (flag) continue;
return false;
}
return true;
}
int main() {
ll n;
while (cin>>n) {
if (MillerRabin(n,5))
cout<<"n is a prime number\n";
else cout<<"n is not a prime number\n";
}
return 0;
}
其中ll mod_pow(ll x, ll y, ll m)實現(xiàn)的是模m意義下的快速冪運算。
擴展閱讀
- 詳細的準確性谎脯、時間復雜度分析和證明請參照https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
