bigint.cpp

命令行方式的硬盘工具 可以在dos和nt下运行。 需要djgpp和vs7.0以上

CBigInt CBigInt::Mod(CBigInt& A)
{
    CBigInt X,Y;
	UINT64 div,num;
//    unsigned long carry=0;
	unsigned i,len;
    X.Mov(*this);
    while(X.Cmp(A)>=0)
    {
		div=X.m_ulValue[X.m_nLength-1];
		num=A.m_ulValue[A.m_nLength-1];
		len=X.m_nLength-A.m_nLength;
		if((div==num)&&(len==0)){X.Mov(X.Sub(A));break;}
		if((div<=num)&&len){len--;div=(div<<32)+X.m_ulValue[X.m_nLength-2];}
		div=div/(num+1);
		Y.Mov(div);
		Y.Mov(A.Mul(Y));
		if(len)
		{
			Y.m_nLength+=len;
			for(i=Y.m_nLength-1;i>=len;i--)Y.m_ulValue[i]=Y.m_ulValue[i-len];
			for(i=0;i<len;i++)Y.m_ulValue[i]=0;
		}
		CBigInt tmp1 = X.Sub(Y) ;
        X.Mov(tmp1);
    }
    return X;
}

unsigned long CBigInt::Mod(unsigned long A)
{
    if(m_nLength==1)return(m_ulValue[0]%A);
    UINT64 div;
    unsigned long carry=0;
    for(int i=m_nLength-1;i>=0;i--)
    {
        div=m_ulValue[i];
		div+=carry*0x100000000LL;
        carry=(unsigned long)(div%A);
    }
    return carry;
}

/****************************************************************************************
从字符串按10进制或16进制格式输入到大数
调用格式：N.Get(str,sys)
返回值：N被赋值为相应大数
sys暂时只能为10或16
****************************************************************************************/
void CBigInt::Get(tstring& str, unsigned int system)
{
    int len=str.length(),k;
    Mov(0);
    for(int i=0;i<len;i++)
    {
       Mov(Mul(system));
       if((str[i]>=_T('0'))&&(str[i]<=_T('9')))k=str[i]-48;
       else if((str[i]>=_T('A'))&&(str[i]<=_T('F')))k=str[i]-55;
       else if((str[i]>=_T('a'))&&(str[i]<=_T('f')))k=str[i]-87;
       else k=0;
       Mov(Add(k));
    }
}

DWORD CBigInt::AtoI(const tstring& str, unsigned int system, int size)
{
	int len=str.length(),k;
	Mov(0);
	if (system != 2)
	{
		for(int i=0;i<len;i++)
		{
			Mov(Mul(system));
			if((str[i]>=_T('0'))&&(str[i]<=_T('9')))k=str[i]-48;
			else if((str[i]>=_T('A'))&&(str[i]<=_T('F')))k=str[i]-55;
			else if((str[i]>=_T('a'))&&(str[i]<=_T('f')))k=str[i]-87;
			else return ERR_INVALID_FORMAT;
			Mov(Add(k));
			if (GetSize() > size)
				return ERR_DATA_SIZE;
		}
	}
	else
	{
		for(int i=0;i<len;i++)
		{
			Mov(Mul(system));
			if((str[i]>=_T('0'))&&(str[i]<=_T('1')))k=str[i]-48;
			else return ERR_INVALID_FORMAT;
			Mov(Add(k));
			if (GetSize() > size)
				return ERR_DATA_SIZE;
		}
	}
	return ERR_SUCCESS;
}

/****************************************************************************************
将大数按10进制或16进制格式输出为字符串
调用格式：N.Put(str,sys)
返回值：无，参数str被赋值为N的sys进制字符串
sys暂时只能为10或16
****************************************************************************************/
void CBigInt::Put(tstring& str, unsigned int system)
{
    if((m_nLength==1)&&(m_ulValue[0]==0)){str=_T("0");return;}
	str=_T("");
    tstring t=_T("0123456789ABCDEF");
    int a;
	TCHAR ch;
	CBigInt X;
	X.Mov(*this);
	while(X.m_ulValue[X.m_nLength-1]>0)
	{
		a=X.Mod(system);
		ch=t[a];
		str.insert((std::string::size_type)0, 1, ch);
		X.Mov(X.Div(system));
	}
}

tstring CBigInt::ItoA(unsigned int system, int size)
{
	tostringstream str;
	tstring thex = _T("0123456789ABCDEF");

//	if((m_nLength==1)&&(m_ulValue[0]==0)){str<< _T("0");return str.str();}
	switch(system)
	{
		case CBigInt::HEX:
			{
				for ( int i = size*8/4 - 1 ; i >= 0; i--)
				{
					int j = ( m_ulValue[i*4 / (sizeof(unsigned long)*8)] >> (i*4 % (sizeof(unsigned long)*8) ) ) & 0XF;
					str<< thex[j];
				}
				break;
			}
		case CBigInt::DEC:
			{
				//CBigInt old = *this;

				//unsigned long *ptmp = &m_ulValue[ size /(sizeof(unsigned long)) ];
				//unsigned int hibit = (1<< (size % (sizeof(unsigned long))) *8 -1);
				//if ( *ptmp & hibit)
				//{
				//	str<<_T("-");
				//	*ptmp &= ~hibit;
				//	for (int i = 0; i < m_nLength; i++)
				//		m_ulValue[i] = ~m_ulValue[i];
				//	Add(1);
				//}
				int a;
				TCHAR ch;
				CBigInt X;
				tstring tstr;
				X.Mov(*this);
				while(X.m_ulValue[X.m_nLength-1]>0)
				{
					a=X.Mod(system);
					ch=thex[a];
					tstr.insert((std::string::size_type)0, 1, ch);
					X.Mov(X.Div(system));
				}
				str<< tstr;

				//*this = old;
			}
			break;
		case CBigInt::BIN:
			{
				for ( int i = size*8-1; i >= 0; i--)
				{
					if (m_ulValue[i / (sizeof(unsigned long)*8) ] & (1 << (i% (sizeof(unsigned long)*8) )) )
					{
						str<< _T("1");
					}
					else
					{
						str<< _T("0");
					}
				}
			}
			break;
	default:
		str<< _T("Base is wrong.");
	}
	return str.str();
}
/****************************************************************************************
求不定方程ax-by=1的最小整数解
调用方式：N.Euc(A)
返回值：X,满足：NX mod A=1
****************************************************************************************/
CBigInt CBigInt::Euc(CBigInt& A)
{
	CBigInt M,E,X,Y,I,J;
	int x,y;
	M.Mov(A);
	E.Mov(*this);
	X.Mov(0);
	Y.Mov(1);
	x=y=1;
	while((E.m_nLength!=1)||(E.m_ulValue[0]!=0))
	{
		I.Mov(M.Div(E));
		J.Mov(M.Mod(E));
		M.Mov(E);
		E.Mov(J);
		J.Mov(Y);
		Y.Mov(Y.Mul(I));
		if(x==y)
		{
			if(X.Cmp(Y)>=0)Y.Mov(X.Sub(Y));
			else{Y.Mov(Y.Sub(X));y=0;}
		}
		else{Y.Mov(X.Add(Y));x=1-x;y=1-y;}
		X.Mov(J);
	}
	if(x==0)X.Mov(A.Sub(X));
	return X;
}

/****************************************************************************************
求乘方的模
调用方式：N.RsaTrans(A,B)
返回值：X=N^A MOD B
****************************************************************************************/
CBigInt CBigInt::RsaTrans(CBigInt& A, CBigInt& B)
{
	CBigInt X,Y;
	int i,j,k;
	unsigned n;
	unsigned long num;
	k=A.m_nLength*32-32;
	num=A.m_ulValue[A.m_nLength-1];
	while(num){num=num>>1;k++;}
	X.Mov(*this);
	CBigInt tmp1,tmp2,tmp3;
	for(i=k-2;i>=0;i--)
	{
		Y.Mov(X.Mul(X.m_ulValue[X.m_nLength-1]));
		Y.Mov(Y.Mod(B));
		for(n=1;n<X.m_nLength;n++)
		{          
			for(j=Y.m_nLength;j>0;j--)Y.m_ulValue[j]=Y.m_ulValue[j-1];
			Y.m_ulValue[0]=0;
			Y.m_nLength++;
			tmp1 = X.Mul(X.m_ulValue[X.m_nLength-n-1]);
			tmp2 = Y.Add(tmp1);
			Y.Mov(tmp2);
			tmp3 = Y.Mod(B);
			Y.Mov(tmp3);
		}
		X.Mov(Y);
		if((A.m_ulValue[i>>5]>>(i&31))&1)
		{
			Y.Mov(Mul(X.m_ulValue[X.m_nLength-1]));
			Y.Mov(Y.Mod(B));
			for(n=1;n<X.m_nLength;n++)
			{          
				for(j=Y.m_nLength;j>0;j--)Y.m_ulValue[j]=Y.m_ulValue[j-1];
				Y.m_ulValue[0]=0;
				Y.m_nLength++;
				tmp1 = Mul(X.m_ulValue[X.m_nLength-n-1]);
				tmp2 = Y.Add(tmp1);
				Y.Mov(tmp2);
				tmp3 = Y.Mod(B);
				Y.Mov(tmp3);
			}
			X.Mov(Y);
		}
	}
	return X;
}

/****************************************************************************************
拉宾米勒算法测试素数
调用方式：N.Rab()
返回值：若N为素数，返回1，否则返回0
****************************************************************************************/
//int CBigInt::Rab()
//{
//	unsigned i,j,pass;
//	for(i=0;i<550;i++){if(Mod(PrimeTable[i])==0)return 0;}
//	CBigInt S,A,I,K;
//	K.Mov(*this);
//	K.m_ulValue[0]--;
//	for(i=0;i<5;i++)
//	{
//		pass=0;
//		A.Mov(rand()*rand());
//		S.Mov(K);
//		while((S.m_ulValue[0]&1)==0)
//		{
//			for(j=0;j<S.m_nLength;j++)
//			{
//				S.m_ulValue[j]=S.m_ulValue[j]>>1;
//				if(S.m_ulValue[j+1]&1)S.m_ulValue[j]=S.m_ulValue[j]|0x80000000;
//			}
//			if(S.m_ulValue[S.m_nLength-1]==0)S.m_nLength--;
//			I.Mov(A.RsaTrans(S,*this));
//			if(I.Cmp(K)==0){pass=1;break;}
//		}
//		if((I.m_nLength==1)&&(I.m_ulValue[0]==1))pass=1;
//		if(pass==0)return 0;
//	}
//	return 1;
//}

/****************************************************************************************
产生随机素数
调用方法：N.GetPrime(bits)
返回值：N被赋值为一个bits位（0x100000000LL进制长度）的素数
****************************************************************************************/
//void CBigInt::GetPrime(int bits)
//{
//	unsigned i;
//	m_nLength=bits;
//begin:
//	for(i=0;i<m_nLength;i++)m_ulValue[i]=rand()*0x10000+rand();
//	m_ulValue[0]=m_ulValue[0]|1;
//	for(i=m_nLength-1;i>0;i--)
//	{
//		m_ulValue[i]=m_ulValue[i]<<1;
//		if(m_ulValue[i-1]&0x80000000)m_ulValue[i]++;
//	}
//	m_ulValue[0]=m_ulValue[0]<<1;
//	m_ulValue[0]++;
//	for(i=0;i<550;i++){if(Mod(PrimeTable[i])==0)goto begin;}
//	CBigInt S,A,I,K;
//	K.Mov(*this);
//	K.m_ulValue[0]--;
//	for(i=0;i<5;i++)
//	{
//		A.Mov(rand()*rand());
//		S.Mov(K.Div(2));
//		I.Mov(A.RsaTrans(S,*this));
//		if(((I.m_nLength!=1)||(I.m_ulValue[0]!=1))&&(I.Cmp(K)!=0))goto begin;
//	}
//}

int CBigInt::GetSize(void)
{
	for (int i = 3; i >=0 ; i--)
	{
		if (m_ulValue[m_nLength-1] & ( 0XFF << (i*8) ))
		{
			return (m_nLength-1)*4 + i+1;
		}

	}
	return 0;
}