原文傳送門：
http://www.wutianqi.com/?p=1253
偽素?cái)?shù)：如果n是一個(gè)正整數(shù)，如果存在和n互素的正整數(shù)a滿足a^n-1≡1(mod n)，我們說(shuō)n是基于a的偽素?cái)?shù)。如果一個(gè)數(shù)是偽素?cái)?shù)，它幾乎肯定是素?cái)?shù)。（即下面的費(fèi)馬小定理）
費(fèi)馬小定理是數(shù)論中的一個(gè)重要定理,其內(nèi)容為: 假如p是質(zhì)數(shù)，且(a,p)=1，那么 a^(p-1) ≡１（mod p） 假如p是質(zhì)數(shù)，且a,p互質(zhì)，那么 a的(p-1)次方除以p的余數(shù)恒等于1。
更多關(guān)于費(fèi)馬小定理請(qǐng)參閱：
http://baike.baidu.com/view/263807.htm?fr=ala0_1
這是Miller Rabbin測(cè)試素?cái)?shù)的代碼模版：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define maxTest 100
__int64 Random(__int64 n)
{
return (__int64)((double)rand()/RAND_MAX*n+0.5);
}
__int64 Modular_Exp(__int64 a, __int64 b, __int64 n) // a^b mod n
{
__int64 ans;
if(b == 0)
return 1;
if(b == 1)
return a%n;
ans = Modular_Exp(a, b/2, n);
ans = ans*ans%n;
if(b%2)
ans = ans*a%n;
}
bool Miller_Rabbin(__int64 n)
{
for(int i=1; i<=maxTest; i++)
{
__int64 a = Random(n-2)+1;
if(Modular_Exp(a, n-1, n) != 1)
return false;
}
return true;
}
int main()
{
srand(time(NULL));
__int64 n;
while(scanf("%I64d", &n)==1)
if(Miller_Rabbin(n))
printf("Primer\n\n");
else
printf("Not Prime\n\n");
return 0;
}
注：
1.Modular_Exp函數(shù)詳細(xì)見(jiàn)：
快速冪取模(點(diǎn)擊查看)
2.這個(gè)算法是概率型算法，而不是確定型算法。不過(guò)多次運(yùn)行后出錯(cuò)概率很小，在實(shí)際應(yīng)用中是可以信賴的。
感謝rakerichard小牛的資料和劉汝佳老師的黑書。
posted on 2010-09-08 14:28
Tanky Woo 閱讀(211)
評(píng)論(0) 編輯 收藏 引用