wizen-coder
10/5/2018 - 1:59 AM

Wilson定理：对于给定的正整数n，判定n是一个素数的充要条件是(n-1)! -1(mod n)。      费尔马小定理：如果p是一个素数，且0<a<p，则a^(p-1)(mod p)。       二次探测定理：如果p是一个素数，且0<x<p，则方程x^21(mod p

Wilson定理：对于给定的正整数n，判定n是一个素数的充要条件是(n-1)! -1(mod n)。 费尔马小定理：如果p是一个素数，且0<a<p，则a^(p-1)(mod p)。 二次探测定理：如果p是一个素数，且0<x<p，则方程x^21(mod p)的解为x=1，p-1。 Carmichael数：费尔马小定理是素数判定的一个必要条件。满足费尔马小定理条件的整数n未必全是素数。有些合数也满足费尔马小定理的条件，这些合数称为Carmichael数。前3个Ca

PrimeMC.cpp
content_copyfile_download
//随机化算法 蒙特卡罗算法 素数测试问题
#include "stdafx.h"
#include "RandomNumber.h"
#include <cmath>
#include <iostream>
using namespace std;
 
//计算a^p mod n,并实施对n的二次探测
void power(unsigned int a,unsigned int p,unsigned int n,unsigned int &result,bool &composite)
{
	unsigned int x;
	if(p == 0)
	{
		result = 1;
	}
	else
	{
		power(a,p/2,n,x,composite);		//递归计算
		result = (x*x)%n;				//二次探测
 
		if((result == 1) && (x!=1) && (x!=n-1))
		{
			composite  = true;
		}
 
		if((p%2)==1)
		{
			result = (result*a)%n;
		}
	}
}
 
//重复调用k次Prime算法的蒙特卡罗算法
bool PrimeMC(unsigned int n,unsigned int k)
{
	RandomNumber rnd;
	unsigned int a,result;
	bool composite = false;
 
	for(int i=1; i<=k; i++)
	{
		a = rnd.Random(n-3)+2;
		power(a,n-1,n,result,composite);
		if(composite || (result!=1))
		{
			return false;
		}
	}
	return true;
}
 
int main()
{
	int k = 10;
	for(int i=1010;i<1025;i++)
	{
		cout<<i<<"的素数测试结果为："<<PrimeMC(i,k)<<endl;
	}
	return 0;
}