bigint.h

一个生成大素数的文件

#ifndef BIGINT_H
#define BIGINT_H

#include <iostream.h>
#include <stdlib.h>

static const unsigned int PrimeTable[302]=
{   3,    5,    7,    11,   13,   17,   19,   23,   29,   31,
    37,   41,   43,   47,   53,   59,   61,   67,   71,   73,
    79,   83,   89,   97,   101,  103,  107,  109,  113,  127, 
    131,  137,  139,  149,  151,  157,  163,  167,  173,  179, 
    181,  191,  193,  197,  199,  211,  223,  227,  229,  233, 
    239,  241,  251,  257,  263,  269,  271,  277,  281,  283, 
    293,  307,  311,  313,  317,  331,  337,  347,  349,  353, 
    359,  367,  373,  379,  383,  389,  397,  401,  409,  419, 
    421,  431,  433,  439,  443,  449,  457,  461,  463,  467, 
    479,  487,  491,  499,  503,  509,  521,  523,  541,  547, 
    557,  563,  569,  571,  577,  587,  593,  599,  601,  607, 
    613,  617,  619,  631,  641,  643,  647,  653,  659,  661, 
    673,  677,  683,  691,  701,  709,  719,  727,  733,  739, 
    743,  751,  757,  761,  769,  773,  787,  797,  809,  811, 
    821,  823,  827,  829,  839,  853,  857,  859,  863,  877,
    881,  883,  887,  907,  911,  919,  929,  937,  941,  947, 
    953,  967,  971,  977,  983,  991,  997,  1009, 1013, 1019, 
    1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087,
    1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 
    1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 
    1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 
    1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381,
    1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 
    1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523,
    1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 
    1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 
    1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 
    1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 
    1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 
    1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 
    1997, 1999};

class BigInt
{
	unsigned int a[64];
	int length;
	friend ostream& operator << (ostream&,const BigInt&);
public:
	BigInt();
	BigInt(const unsigned int&);
	BigInt(const BigInt&);
	BigInt(unsigned char *,int);
	int Length() {return length;}
	unsigned int operator [](int i) {return a[i];}
	BigInt& operator = (const BigInt&);
	BigInt& operator = (const unsigned int&);
	bool operator < (const BigInt&);
	bool operator == (const unsigned int&);
	BigInt operator - (const BigInt&);
	BigInt operator - (const unsigned int&);
	BigInt& operator += (const BigInt&);
	BigInt& operator += (const unsigned int&);
	BigInt operator * (const BigInt&);
	BigInt operator * (const unsigned int&);
	BigInt& operator <<= (const unsigned int&);
	BigInt operator >> (const unsigned int&);
	BigInt operator % (BigInt&);
	unsigned int operator % (const unsigned int&);
	BigInt DIV(BigInt&,BigInt&);
	BigInt PowerMod(const BigInt&,BigInt&);
	void GetRand(const unsigned int&);
	bool IsPrime();
	void GetPrime(const unsigned int&);
	BigInt Euc(BigInt&,BigInt&);
};

inline BigInt::BigInt()
{
	length=0;
}

inline BigInt::BigInt(const unsigned int& X)
{
	if(X)
	{
		length=1;
		a[0]=X;
	}
	else length=0;
}

inline BigInt::BigInt(const BigInt& X)
{
	length=X.length;
	for(int i=0;i<length;i++)
		a[i]=X.a[i];
}

inline BigInt::BigInt(unsigned char *c,int len)
{
	length=len>>2;
	int pad=len&0x3,i=0,j=length-1;
	if(pad)
	{
		length++;
		a[length-1]=0;
		while(pad)
		{
			a[length-1]<<=8;
			a[length-1]|=c[i];
			i++;
			pad--;
		}
	}
	for(;j>=0;j--,i+=4)
		a[j]=((unsigned int)c[i]<<24)|((unsigned int)c[i+1]<<16)|((unsigned int)c[i+2]<<8)|(unsigned int)c[i+3];
}

inline BigInt& BigInt::operator = (const BigInt& X)
{
	length=X.length;
	for(int i=0;i<length;i++)
		a[i]=X.a[i];
	return *this;
}

inline BigInt& BigInt::operator = (const unsigned int& X)
{
	if(X)
	{
		length=1;
		a[0]=X;
	}
	else length=0;
	return *this;
}

inline bool BigInt::operator < (const BigInt& X)
{
	if(length<X.length) return true;
	if(length>X.length) return false;
	for(int i=length-1;i>=0;i--)
		if(a[i]<X.a[i])	return true;
		else if(a[i]>X.a[i]) return false;
	return false;
}

inline bool BigInt::operator == (const unsigned int& X)
{
	return (length==1 && X==a[0]) || (length==0 && X==0);
}

inline BigInt BigInt::operator - (const BigInt& X)
{
	int borrow=0,i;
	BigInt M=*this;
	for(i=0;i<X.length;i++)
		if(a[i]<X.a[i]+borrow)
		{
			M.a[i]+=((unsigned _int64)1<<32)-X.a[i]-borrow;
			borrow=1;
		}
		else
		{
			M.a[i]-=X.a[i]+borrow;
			borrow=0;
		}
	while(borrow)
	{
		if(M.a[i]==0)
			M.a[i]=0xffffffff;
		else
		{
			M.a[i]--;
			borrow=0;
		}
		i++;
	}
	while(M.length && M.a[M.length-1]==0) M.length--;
	return M;
}

inline BigInt BigInt::operator - (const unsigned int& X)
{
	BigInt M=*this;
	if(M.a[0]<X)
	{
		M.a[0]+=((unsigned int)1<<32)-X;
		int i=1;
		while(M.a[i]==0)
		{
			M.a[i]=0xffffffff;
			i++;
		}
		M.a[i]--;
	}
	else M.a[0]-=X;
	if(M.a[length-1]==0) M.length--;
	return M;
}

inline BigInt& BigInt::operator += (const BigInt& X)
{
	BigInt M;
	unsigned _int64 temp;
	int carry=0,i;
	if(length<X.length)
	{
		M=*this;
		*this=X;
	}
	else M=X;
	for(i=0;i<M.length;i++)
	{
		temp=(unsigned _int64)a[i]+M.a[i]+carry;
		a[i]=temp;
		carry=temp>>32;
	}
	while(carry && i<length)
	{
		temp=(unsigned _int64)a[i]+carry;
		a[i]=temp;
		carry=temp>>32;
		i++;
	}
	if(carry)
	{
		a[length]=1;
		length++;
	}
	return *this;
}

inline BigInt& BigInt::operator += (const unsigned int& X)
{
	if(length)
	{
		unsigned _int64 temp=a[0];
		temp+=X;
		a[0]=temp;
		if(temp>0xffffffff)
		{
			int carry=1,i=1;
			while(i<length && a[i]==0xffffffff)
			{
				a[i]=0;
				i++;
			}
			if(i==length)
			{
				a[i]=1;
				length++;
			}
			else a[i]++;
		}
	}
	else *this=X;
	return *this;
}

inline BigInt BigInt::operator * (const BigInt& X)
{
	BigInt temp;
	if(X.length && length)
	{
		temp.length=length+X.length-1;
		unsigned _int64 carry=0,tt;
		for(int i=0;i<temp.length;i++)
		{
			tt=carry;
			carry=0;
			for(int j=(i<X.length?0:i-X.length+1);j<=i && j<length;j++)
			{
				tt+=(unsigned _int64)this->a[j]*X.a[i-j];
				carry+=tt>>32;
				tt&=0xffffffff;
			}
			temp.a[i]=tt;
		}
		if(carry)
		{
			temp.a[temp.length]=carry;
			temp.length++;
		}
	}
	return temp;
}

inline BigInt BigInt::operator * (const unsigned int& X)
{
	BigInt M;
	if(length && X)
	{
		unsigned _int64 temp,carry=0;
		int i;
		M.length=length;
		for(i=0;i<length;i++)
		{
			temp=(unsigned _int64)a[i]*X+carry;
			M.a[i]=temp;
			carry=temp>>32;
		}
		if(carry)
		{
			M.a[i]=carry;
			M.length++;
		}
	}
	return M;
}

inline BigInt& BigInt::operator <<= (const unsigned int& X)
{
	if(length)
	{
		int i;
		length+=X;
		for(i=length-1;i>=X;i--)
			a[i]=a[i-X];
		for(i=0;i<X;i++)
			a[i]=0;
	}
	return *this;
}

inline BigInt BigInt::operator >> (const unsigned int& X)
{
	BigInt M;
	if(length>X)
	{
		M=*this;
		M.length-=X;
		for(int i=0;i<M.length;i++)
			M.a[i]=M.a[i+X];
	}
	return M;
}

inline BigInt BigInt::operator % (BigInt& X)
{
	BigInt Y;
	if(!(*this<X))
	{
		int i;
		unsigned int yy;
		Y=*this>>(length-X.length);
		unsigned _int64 tt;
		for(i=length-X.length;i>=0;i--)
		{
			if(!(Y<X))
			{
				do {
					tt=Y.a[Y.length-1];
					if(Y.length!=X.length) tt=(tt<<32)+Y.a[Y.length-2];
					yy=tt/((unsigned _int64)X.a[X.length-1]+1);
					if(!yy) yy=1;
					Y=Y-X*yy;
				}while(!(Y<X));
			}
			if(i!=0)
			{
				Y<<=1;
				Y+=a[i-1];
			}
		}
	}
	else Y=*this;
	return Y;
}

inline BigInt BigInt::DIV(BigInt& X,BigInt& Y)
{
	BigInt M;
	if(!(*this<X))
	{
		int i;
		unsigned int yy;
		Y=*this>>(length-X.length);
		M.length=length-X.length+1;
		unsigned _int64 tt,quoa;
		for(i=M.length-1;i>=0;i--)
		{
			quoa=0;
			if(!(Y<X))
			{
				do {
					tt=Y.a[Y.length-1];
					if(Y.length!=X.length) tt=(tt<<32)+Y.a[Y.length-2];
					yy=tt/((unsigned _int64)X.a[X.length-1]+1);
					if(!yy) yy=1;
					quoa+=yy;
					Y=Y-X*yy;
				}while(!(Y<X));
			}
			M.a[i]=quoa;
			if(i!=0)
			{
				Y<<=1;
				Y+=a[i-1];
			}
		}
		if(M.a[M.length-1]==0) M.length--;
	}
	return M;
}

inline BigInt BigInt::PowerMod(const BigInt& M,BigInt& N)
{
	BigInt result=1;
	for(int i=M.length-1;i>=0;i--)
		for(int j=31;j>=0;j--)
		{
			result=result*result;
			result=result%N;
			if(M.a[i]&(1<<j))
			{
				result=result*(*this);
				result=result%N;
			}
		}
	return result;
}

inline void BigInt::GetRand(const unsigned int& len)
{
	length=len;
	for(int i=0;i<len;i++)
		a[i]=(rand()<<16)+rand();
	a[0]|=1;
	a[len-1]|=0x80000000;
}

bool BigInt::IsPrime()
{
	int i;
	BigInt M;
	for(i=0;i<302;i++)
		if(*this%PrimeTable[i]==0) return false;
	for(i=0;i<5;i++)
	{
		M.GetRand(1);
		if(!(M.PowerMod(*this-1,*this)==1)) return false;
	}
	return true;
}

inline ostream& operator << (ostream& os,const BigInt& X)
{
	if(X.length)
	{
		os.setf(ios::hex|ios::uppercase);
		for(int i=X.length-1;i>=0;i--)
		{
			os.width(8);
			os.fill('0');
			os<<X.a[i];
		}
	}
	else os<<0;
	return os;
}

inline unsigned int BigInt::operator % (const unsigned int& X)
{
	unsigned _int64 tt=0;
	for(int i=length-1;i>=0;i--)
	{
		tt=(tt<<32)+a[i];
		tt%=X;
	}
	return (unsigned int)tt;
}

inline void BigInt::GetPrime(const unsigned int& X)
{
	GetRand(X);
	while(!IsPrime()) *this+=2;
}

inline BigInt BigInt::Euc(BigInt& X,BigInt& Y)
{
	BigInt A=X,B=*this,Q,R,X1=0,X2=1;
	int sign_1=1,sign_2=1;
	while(!(B==0))
	{
		Q=A.DIV(B,R);
		A=B;
		B=R;
		R=X2;
		X2=X2*Q;
		if(sign_1==sign_2)
			if(X2<X1) X2=X1-X2;
			else
			{
				X2=X2-X1;
				sign_2=1-sign_2;
			}
		else
		{
			X2+=X1;
			sign_1=sign_2;
			sign_2=1-sign_2;
		}
		X1=R;
	}
	if(!sign_1) X1=X-X1;
	Y=A;
	return X1;
}

#endif