Miller-Rabin素數測試

             由費馬小定理可知，若n為素數，且a是整數，則滿足a^n≡a(mod n)。若存在正整數a不滿足a^n≡a(mod n)，那麼n是合數。

定義：令a是一正整數，若n是合數且滿足a^n≡a(mod n)，則n稱為以a為基的僞素數。

算法原理：Miller-Rabin素數測試算法基于費馬小定理：假如n是素數，且gcd(a,n)=1,那麼a^(n-1)≡1(mod n)。如果a^(n-1)≡1(mod n)(a為任意小于n的正整數)，則可近似認為n為素數，取多個底進行試驗，次數越多，n為素數的機率越大。

代碼：

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;
typedef long long int64;
#define TIMES 5

int64 random(int64 n)
{
	return (int64)((double)rand()/RAND_MAX*n+0.5);
}

int64 multi(int64 a,int64 b,int64 m) //a*b%m
{
	int64 ans=0;
	while(b)
	{
		if(b&1)
			ans=(ans+a)%m;
		b>>=1;
		a=(a<<1)%m;
	}
	return ans;
}

int64 kpow(int64 x,int64 n,int64 m) //x^n%m
{
	int64 ans=1;
	while(n)
	{
		if(n&1)
			ans=multi(ans,x,m);
		n>>=1;
		x=multi(x,x,m);
	}
	return ans;
}

bool miller_rabin(int64 n)
{
	for(int64 i=1;i<=TIMES;i++)
	{
		int64 x=random(n-2)+1;
		if(kpow(x,n-1,n)!=1)
			return false;
	}
	return true;
}

int main()
{
	int64 x;
	while(cin>>x)
	{
		if(miller_rabin(x))
			cout<<"YES\n";
		else
			cout<<"NO\n";
	}
	return 0;
}
           

題目：http://poj.org/problem?id=3641