如果n是一個正整數(shù)，如果存在和n互素的正整數(shù)a滿足a^n-1≡1(mod n)，我們說n是基于a的偽素數(shù)。如果一個數(shù)是偽素數(shù)，它幾乎肯定是素數(shù)。
以下是我的miller_rabbin素數(shù)測試的代碼：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define maxTest 5
typedef long long int64;
int64 random(int64 n)
{
return (int64)((double)rand()/RAND_MAX*n+0.5);
}
int64 mod_exp(int64 a,int64 b,int64 n)
{
long ans;
if(b==1) return a%n;
ans=mod_exp(a,b/2,n);
if(b%2==0) return ans*ans%n;
else return ans*ans%n*a%n;
}
bool miller_rabbin(int64 n)
{
for(long i=1;i<=maxTest;i++)
{
long a=random(n-2)+1;
if(mod_exp(a,n-1,n)!=1) return false;
}
return true;
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
srand(time(NULL));
int64 n;
while(scanf("%I64d",&n)==1)
if(miller_rabbin(n))
printf("True\n\n");
else printf("False\n\n");
return 0;
}
posted on 2010-02-20 16:02
lee1r 閱讀(1603)
評論(0) 編輯 收藏 引用 所屬分類:
算法與數(shù)據(jù)結(jié)構(gòu)