Miller-Rabin(米勒羅賓)素性測試

算法思想

對于大于2的素數(shù)n丸相,將n-1拆分為

其中s和d是正整數(shù)且d是奇數(shù)搔确。對所有整數(shù)a(0<a<n),下面兩個式子一定有一個成立:![](http://latex.codecogs.com/svg.latex?a^d\equiv 1 \pmod{n}) ![](http://latex.codecogs.com/svg.latex?a{2r*d}\equiv -1 \pmod{n} (for \ some \ r \ that \ 0\leq r \leq s-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意義下的快速冪運算。

擴展閱讀

最后編輯于
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末葱跋,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子源梭,更是在濱河造成了極大的恐慌娱俺,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,946評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件废麻,死亡現(xiàn)場離奇詭異荠卷,居然都是意外死亡,警方通過查閱死者的電腦和手機烛愧,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評論 3 399
  • 文/潘曉璐 我一進店門油宜,熙熙樓的掌柜王于貴愁眉苦臉地迎上來掂碱,“玉大人,你說我怎么就攤上這事验庙《ニ保” “怎么了社牲?”我有些...
    開封第一講書人閱讀 169,716評論 0 364
  • 文/不壞的土叔 我叫張陵粪薛,是天一觀的道長。 經(jīng)常有香客問我搏恤,道長违寿,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,222評論 1 300
  • 正文 為了忘掉前任熟空,我火速辦了婚禮藤巢,結果婚禮上,老公的妹妹穿的比我還像新娘息罗。我一直安慰自己掂咒,他們只是感情好,可當我...
    茶點故事閱讀 69,223評論 6 398
  • 文/花漫 我一把揭開白布迈喉。 她就那樣靜靜地躺著绍刮,像睡著了一般。 火紅的嫁衣襯著肌膚如雪挨摸。 梳的紋絲不亂的頭發(fā)上孩革,一...
    開封第一講書人閱讀 52,807評論 1 314
  • 那天,我揣著相機與錄音得运,去河邊找鬼膝蜈。 笑死,一個胖子當著我的面吹牛熔掺,可吹牛的內(nèi)容都是我干的饱搏。 我是一名探鬼主播,決...
    沈念sama閱讀 41,235評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼置逻,長吁一口氣:“原來是場噩夢啊……” “哼推沸!你這毒婦竟也來了?” 一聲冷哼從身側響起诽偷,我...
    開封第一講書人閱讀 40,189評論 0 277
  • 序言:老撾萬榮一對情侶失蹤坤学,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后报慕,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體深浮,經(jīng)...
    沈念sama閱讀 46,712評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,775評論 3 343
  • 正文 我和宋清朗相戀三年眠冈,在試婚紗的時候發(fā)現(xiàn)自己被綠了飞苇。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片菌瘫。...
    茶點故事閱讀 40,926評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖布卡,靈堂內(nèi)的尸體忽然破棺而出雨让,到底是詐尸還是另有隱情,我是刑警寧澤忿等,帶...
    沈念sama閱讀 36,580評論 5 351
  • 正文 年R本政府宣布栖忠,位于F島的核電站,受9級特大地震影響贸街,放射性物質(zhì)發(fā)生泄漏庵寞。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,259評論 3 336
  • 文/蒙蒙 一薛匪、第九天 我趴在偏房一處隱蔽的房頂上張望捐川。 院中可真熱鬧,春花似錦逸尖、人聲如沸古沥。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,750評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽岩齿。三九已至,卻和暖如春逞频,著一層夾襖步出監(jiān)牢的瞬間纯衍,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,867評論 1 274
  • 我被黑心中介騙來泰國打工苗胀, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留襟诸,地道東北人。 一個月前我還...
    沈念sama閱讀 49,368評論 3 379
  • 正文 我出身青樓基协,卻偏偏與公主長得像歌亲,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子澜驮,可洞房花燭夜當晚...
    茶點故事閱讀 45,930評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 轉載自Matrix大牛一個數(shù)是素數(shù)(也叫質(zhì)數(shù))陷揪,當且僅當它的約數(shù)只有兩個——1和它本身。規(guī)定這兩個約數(shù)不能相同杂穷,因...
    Gitfan閱讀 2,080評論 0 1
  • 回溯算法 回溯法:也稱為試探法悍缠,它并不考慮問題規(guī)模的大小,而是從問題的最明顯的最小規(guī)模開始逐步求解出可能的答案耐量,并...
    fredal閱讀 13,675評論 0 89
  • 最近迷上了英文原版的書籍飞蚓,哈利波特,冰與火之歌廊蜒,暮光之城趴拧,福爾摩斯等所有通俗小說都想入手一套溅漾。看了京東當當亞馬遜之...
    向清1314閱讀 227評論 0 4
  • 別院深深暮胧,夏木陰陰,擇石為桌挂谍,悠然待客叔壤。 關于夏天瞎饲,關于蟬鳴口叙,關于那些老院子,我總固執(zhí)地認為:她美得失真嗅战,美得局氣...
    木頭加加閱讀 482評論 1 1
  • 今天的晨讀文章是如何成為一個社交高手妄田,讓我突然就聯(lián)想到前段時間看過的一本書《蔡康永的說話之道》,這本書是以一個個小...
    小V姑娘閱讀 198評論 0 0