如果n是一个正整数，如果存在和n互素的正整数a满足a^n-1≡1(mod n)，我们说n是基于a的伪素数。如果一个数是伪素数，它几乎肯定是素数。
以下是我的miller_rabbin素数测试的代码：
#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 阅读(1552)
评论(0) 编辑 收藏 引用 所属分类:
算法与数据结构