算法思想

對(duì)于大于2的素?cái)?shù)n，將n-1拆分為

準(zhǔn)確性

所有的奇合數(shù)都有很多的a滿足"witness"的條件，不過(guò)目前為止還沒(méi)有確定的算法能夠直接根據(jù)n生成這樣的數(shù)a，于是我們可以多次隨機(jī)抽取1~n-1中的整數(shù)并做測(cè)試。
當(dāng)我們k次隨機(jī)選取a測(cè)試時(shí)，一個(gè)合數(shù)被該算法判定為素?cái)?shù)的概率是4^(-k)。

一種實(shí)現(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)實(shí)現(xiàn)的是模m意義下的快速冪運(yùn)算。

擴(kuò)展閱讀

• 詳細(xì)的準(zhǔn)確性、時(shí)間復(fù)雜度分析和證明請(qǐng)參照https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test