素数的判定.cpp

素数的判定（概率算法）

#include <iostream>
#include <time.h>
#include <math.h>
#include <string>
using namespace std;
string GJD_CF(_int64 int64_1,_int64 int64_2)
{
	string v1="",v2="";
	while (int64_1!=0)
	{
		v1=(char)((int64_1%10)+48)+v1;
		int64_1=(int64_1-(int64_1%10))/10;
	}
	while (int64_2!=0)
	{
		v2=(char)((int64_2%10)+48)+v2;
		int64_2=(int64_2-(int64_2%10))/10;
	}
	string s1="",s2="",v3="",result;
	//将v1,v2倒置
	int i;
	for (i=v1.length()-1;i>=0;i--)
		s1+=v1[i];
	for (i=v2.length()-1;i>=0;i--)
		s2+=v2[i];
	v1=s1;
	v2=s2;
	for (i=0;i<v1.length()+v2.length();i++)
		v3+="0";
	for (i=0;i<v1.length();i++)
	{
		int jingwei=0;
		int j;
		for (j=0;j<v2.length();j++)
		{
			int t1,t2,t3,t4;
			t1=v1[i]-48;
			t2=v2[j]-48;
			t3=v3[i+j]-48;
			t4=t1*t2+t3+jingwei;
			jingwei=0;
			if (t4>=10)
			{
				jingwei=t4/10;
				t4=t4%10;
			}
			v3[i+j]=(char)(t4+48);
		}
		if (jingwei!=0)
			v3[v2.length()+i]=(char)(jingwei+48);
	}
	result="";
	for (i=v3.length()-1;i>=0;i--)
		result+=v3[i];
	while (result[0]=='0'&&result.length()>1)
		result.erase(0,1);
	return result;
}
_int64 str_Mod_Int64(string val,_int64 n)
{
	int i=0;
	_int64 temp=0,yu;
	string v3="";
	while (temp<n&&val.length()>0)
	{
		temp=temp*10+val[0]-48;
		val.erase(0,1);
	}
	while (temp>=n)
	{
		v3=v3+(char)(temp/n+48);
		yu=temp%n;
		while (yu!=0)
		{
			val=(char)((yu%10)+48)+val;
			yu=(yu-(yu%10))/10;
		}
		temp=0;
		while (temp<n&&val.length()>0)
		{
			temp=temp*10+val[0]-48;
			val.erase(0,1);
		}
	}
	return temp;
}
_int64 modular_exponentiation(_int64 a,_int64 b,_int64 n)
//输入a,b和n,返回a^b mod n的值
{
	_int64 d,t;
	d=1;
	t=a;
	while (b>0)
	{
		if (t==1)
			return d;
		if ((b%2)==1)
		{
			d=str_Mod_Int64(GJD_CF(d,t),n);
		}
		b=b/2;
		//t*t可能超界,所以这里采用模区幂运算
		//t=t^2%n;
		t=str_Mod_Int64(GJD_CF(t,t),n);
	}
	return d;
}

//输入被测试的数n和实验基数的个数。若n是合数返回false；若n是素数返回true;
bool miller_rabin(_int64 n,int s)
{
	_int64 i,a;
	srand( (unsigned)time( NULL ) );
	for (i=1;i<=s;i++)
	{
		a=((double)rand()/(double)RAND_MAX)*(n-1)+1;
		if (modular_exponentiation(a,n-1,n)!=1)
			return false;
	}
	return true;
}

int main()
{
	cout<<miller_rabin(411522630413,12)<<endl;
	return 0;
}