mrprime.cpp

Miller rabin素性检测算法源代码

#include <iostream>
#include "mmath.h"
#include "random.h"

using namespace std;
	
bool witness(int n,int a)
{
	int m = n-1,t = 0,u;
	
	while(m%2==0)
		t++,m/=2;
	
	u = m;
	
	int x = MMath::power(a,n,u);
	int y;
		
	for(int i=1;i<=t;i++){
		
		y = (x*x)%n;
					
		if(y==1&&x!=1&&x!=n-1)
			return true;	
			
		x = y;
	}
	
	if(y==1)
		return false;
	else 
		return true;
}
	
	
bool mr(int n,int t)
{
	while(--t!=0){
		
		Random *r = new Random();
	
		if(witness(n,r->random(2,n-1)))
			return false;
	}
	return true;
}

int main()
{
	while(1){
		
		int n;
	
		scanf("%d",&n);
	
		if(mr(n,10))
			printf("n is a prime\n");
		else 
			printf("n is not a prime\n");
	}		
	
	return 0;
}