mmath.h

Miller rabin素性检测算法源代码

/*
 * Basing on the two theories:
 * 1,(x*y)%z=((x%z)*(y%z))%z
 * 2,(x^y)%z=((x%z)^y)%z
 * To solve the y=(g^x)%p problem
 * left shifting x until x become 
 * 0,compute g^x by computing 
 * k=(g^(x/2)%p) and g^x=k*k or g^x=k*k*g;
 * so this algorithm is O(lgn) which is also linear;
 * This is a simple and recursive algorithm.
*/
#ifndef MMATH_H
#define MMATH_H

class MMath{
	
	public:
		
	static int power(int g,int p,int n){

		int s,u;

		if(n==0)return 1;
		else {
			s = power(g,p,n>>1);
			u = s*s;
			if(n%2==0)
				return u%p;
			else 
				return u*g%p;
		}
	}
	
	static int gcd(int n,int m){
		if(m<n)return gcd(m,n);
		if(m%n==0)return n;
		return gcd(m%n,n);
	}
	
	static bool jprime1(int n){
		if(power(2,n,n-1)!=1)return false;
		else return true;
	}	
		
};

#endif